For reference: I have had sporadic problems with the Cisco VPN client, which I installed after installing Parallels (3.0, 4128). For me, the solution was "ifconfig fw0 down" -- none of the other stuff, to do with restarting the kext, appears to have been either necessary or relevant.
It is interesting that fw0 has shown up a few times lately in questions about networking failures. That is a trend.
What is maddening is that this issue has been around since the beginning. I had to de-install and re-install PWS and Cisco also (several times). Downing the one interface does work but this is a pain and problematic in some cases. By comparison VMWare, while it warns of this potential issue, does not cause this problem. My final fix was to de-install both (leave the HD images), reboot, re-install PWS, reboot, re-install Cisco, reboot, and to script the downing of the fw0 interface. After that the host VPN started to work again.
Just out of curiosity, under parallels preferences (not vm edit but the real preferences) click on the network tab. Are the two check boxes checked or not checked?
I'm having this problem too. The other problem I had was that, when I migrated a couple of my Virtual PC VMs, they were created with Shared Networking by default, which caused an error when I tried to start them. Changing Networking to Bridged Ethernet fixed this problem, but now this appears to be the only network option available in these VMs. Could these problems be related? Oh, it also adds two copies of a configuration called "Ethernet Adapter ((null))" to my Mac's Network Port Configurations, which seems rather an odd thing to do.