I recently upgraded to Virtual Server 2005 SP1 for the performance benefits, among other things. Unfortunately, I also lost the ability to connect to anything other than my host machine, rendering my server basically worthless.
It turns out the problem was Norton Internet Security, which I had installed after the initial install but before this recent upgrade. According to the Taylor on the MSFT newsgroups, "we have seen this problem with Norton and other similar programs, they attempt to prevent our Network Driver from installing as a lot of malware uses the same type of driver."
The real problem is that there is no indication that this was a problem - the VM's network appears to be connected, and you can ping to and from the host machine. This led me to initially suspect a firewall, but the problem persisted even after I uninstalled Norton and disabled the Windows Firewall. The problem was also present in machines running under Virtual PC 2004.
So if you're having problems with networking on a virtual machine and you have Norton Internet Security (or a similar third-party product) installed, remove it and reinstall VS2005.