A system and method scales private Virtual Local Area Networks (VLANs) to a large computer network, such as a very large Metropolitan Area Network (MAN), so that the VLAN designations can be re-used across the network. In the illustrative embodiment, the MAN includes different groups of Layer 2 (L2) switches that are logically organized into Islands interconnected by an interconnect fabric. Within each Island, Customer-Equipment VLAN Identifiers (CE-VLAN IDs) are mapped to MAN Provider-Equipment VLAN IDs (PE-VLAN IDs). The PE-VLAN IDs defined within the MAN support the creation of Private VLANs. Each Private VLAN includes one Primary VLAN, one Isolated VLAN and may include one or more Community VLANs. Different PE-VLAN IDs may be used as the Primary, Isolated and Community VLANs in different Islands. Nonetheless, the Primary, Isolated and Community VLANs from all of the Islands are assigned the same Virtual Circuit IDs, which are loaded into encapsulated frames traversing the interconnect fabric, thereby maintaining the message's association with the Primary, Isolated and Community VLANs.