Are you using the VM Hub or do you have it in modem mode with your own router? If the latter (modem mode) you need to make sure you're using VM's DNS when setting up the box for the first time. Once set up you can go back to your own choice of DNS (e.g. OpenDNS, Google, etc.)
If you're using the hub, give it a few hours and if still no joy report a fault.
Also try going to Network Settings and connecting to the VM service manually. If you haven't done so already, a box reboot is also worth a shot.