I'm not sure if the use of the VM plays a role here. But since the OP mentioned it (and it would have helped to know which VM technology, MS Virtual PC?, VirtualBox?, VMware?), make sure your VMs are using compatible virtual network adapter configurations. For example, you wouldn't want a mix of bridged and unbridged (NAT'd) for each VM or else they would end up on different subnets.
That aside, you’re back to all the usual checks; they must use the same workgroup name, be using the same subnet, no third party firewalls, each should be using the same username/password, yada yada.