1. A computer-implemented method for configuring intercommunications between computing systems of a program execution service, the method comprising: receiving an indication of a program to be executed on behalf of a customer of a program execution service, the program to be executed on one of multiple virtual machines that are hosted by a first computing system associated with the program execution service, the first computing system being one of multiple computing systems of a first of multiple physical networks of the program execution service, the multiple physical networks being configured to communicate via an interconnection network, the interconnection network having multiple gateway networking devices that each connect at least at least one of the multiple physical networks to the interconnection network and having multiple internal networking devices that facilitate communication over the interconnection network; determining a virtual network to which the indicated program is to be associated based at least in part on the customer of the program execution service, the determined virtual network including computing systems on multiple of the physical networks of the program execution service that each host one or more virtual machines executing one or more programs on behalf of the customer; and automatically enabling the indicated program on the one virtual machine of the first computing system to intercommunicate with other computing systems on the determined virtual network, by identifying a first networking identifier that is associated with the determined virtual network and that is based on a virtual local area networking protocol for use with the first physical network, and identifying a distinct second networking identifier that is associated with the determined virtual network and that is based on a distinct label switching protocol for use with the interconnection network; configuring a virtual machine communication manager module for the first computing system to associate communications from the indicated program on the one virtual machine with the determined virtual network, the associating of the communications with the determined virtual network including modifying the communications to include the first networking identifier, such that communications including the first networking identifier on the first physical network are not forwarded to computing systems of the first physical network that do not have a hosted virtual machine associated with the determined virtual network; configuring a gateway networking device connecting the first physical network and the interconnection network to forward communications associated with the determined virtual network over the interconnection network in accordance with the label switching protocol by modifying communications on the first physical network that include the first networking identifier so as to include the second networking identifier; and sending a communication from the indicated program to a destination computing system of a second physical network that is a part of the determined virtual network, the sending including forwarding the communication over the first physical network using the first networking identifier and forwarding the communication over the interconnection network to the second physical network using the second networking identifier.