While I am a huge fan of Virtual Box, work supplies us with Parallels and a Windows 7 virtual machine. I find Parallels to be slower but it works overall just fine. Recently I wanted to install a Linux VM so I installed Virtual Box on my Mac. As always, Virtual Box installs virtual network cards (vnic) and makes some modifications to the underlying OS.
My Parallels Windows 7 VM was running using shared networking. I needed to have it be accessible outside the host so I switched it to Bridged Networking using the host's Ethernet device. At that point something weird happened: the VM would connect to the network, get an IP address assigned, but it would report failing to get to the network gateway. It failed to see the outside Internet. Trying all sorts of Windows networking tricks did nothing to alleviate the situation, with Windows reporting that 'unauthenticated domain'.
The solution: removing Virtual Box using the script that comes on its dmg installer, restarting the Mac host and starting Parallels again. Suddenly I was able to connect to the network just fine.
Hope it helps others.