I also am having this problem, and changing network.xml does not fix it for me, unfortunately. I'm running MacOS 10.6.1 (Snow Leopard), and my guest VM is Windows XP. My version of Parallels is 4.0.3848.
Now that I have made the change, here's the relevant section of that file:
After making this change, I rebooted my Mac and restarted Parallels, but I still get the same error mentioned above when going to Windows Update.
All other internet accesses work fine under my guest VM.