I had a friend that had a problem similiar to this and it turned out to be a worm. The one site he could not get to was Google.com althought I'm not sure if his AIM was infected.
<long pause>
I just got off the phone with him but he can't remember the name of the worm. He said it was called Qt worm or something similiar. He got a tool for it at
www.sarc.com (their site is really slow right now so it's going to be hard luck going searching the site) that helped to clean his machine up.
I'm guessing here but I think this is what he used:
http://www.sarc.com/avcenter/venc/da...oval.tool.html
He did say he had to remove a few keys in the registry but he couldn't tell me which ones they were.. (he's extremely intelligent but somewhat forgetful).
The funny thing is he's running NAV 8 Corp on his machine (and it was up to date) and it never picked up the virus.