Start up Parallels and select your Windows virtual machine, but don't start it up. If it doesn't show a screen of your virtual machine settings, click the Property Page View button. Then click on Network Adapter. On the right side under Emulation, what is the setting? The 1970 update introduced a new setting called Shared Networking. This seems to be the best option, as it works independently of the Internet Sharing of OS X (which is pretty picky, and doesn't work if you're connected to a VPN).
If your virtual machine is not set to Shared Networking, select it and give that a try.
Also, have you installed Parallels Tools within the VM? If you haven't done that, lots of stuff won't work well or at all. Fire up the VM, and when it's fully up and running, click the VM button at the top of the screen (the Mac screen, not the VM screen), then click Install Parallels Tools.
If after all that you still can't get to the internet from the virtual machine, then make sure the network adapter in Windows is set entirely to defaults (Use DHCP, Use gateway on remote network, Use DNS servers provided by DHCP, etc.).
And if that doesn't work, go to the VM and click Start, Run, and type "cmd" (without the quotes) in the small window that opens up. A command line session window will open. Type "ipconfig /all" in that window and post the results.
Good luck.