Win98 Registry Update/Can’t View Web Pgs

In an effort to improve poor performance of my girlfriend’s laptop, we deleted some spyware we discovered using Windows’ remove programs function. Immediately upon removal, the computer did a reboot, and did what I believe was a Windows Registry Update [?]. Soon afterwards, we found that while we could connect to the Internet, we weren’t able to view any web pages (the dreaded ‘page not found’ message came up for every site we tried). We also can’t download email from the Earthlink server. Earthlink talked us through deleting our network connection setup and creating a new one, but that didn’t help, and now they’re basically washed their hands of the issue. Anyone have any idea whether the registry update would have anything to do with this, or have any ideas as to how we can try to correct it?