Installing Safari 3 Beta (mac) seems to prevent Parallels from accessing the oustide network. Uninstalling fixed the problem.
I installed Safari 3 and restarted. No networking problems. (Using Shared Networking) and newest Parallels V3 build.
I had the same issue at first, then I disconnected and reconnected Network driver, and all set. I'm good now.