Yesterday MacOSX's update told me there was a Firmware update for my mac. Great, I thought, except that it required me to reboot my mac. So I did that and suddenly the networking in parallels was broken. It wouldn't work - at all.
Here's what you need to lookout for - the Blue systray icon in windows disappears. In MacOSX network status preferences, the Parallels NAT device is Red.
If you have the same problem as me - there's only one solution listed in the FAQ. Uninstall Parallels, reboot your mac, then reinstall Parallels. This forces the network driver to be removed and readded. This process will -not- wipe your installed parallels virtual machine, just the parallels software.
The uninstall and install progarm is in the parallels dmg - which you can download from their website.