I ran into a problem at my in-laws house last night. I was on their laptop, and every time I opened IE it brought me to a site claiming I had spyware installed, and the only way to get rid of it was to click OK on the popup and install their anti-spyware software. This, in fact, WAS the spyware. I ran a bunch of anti-virus (Yahoo! Anti Virus) and anti-spyware (SpyBot S&D), but they didn't fix it. I found the below site while Googling, and it worked.
Technibble.com
You'll need to download a zip file, restart in Safe Mode, run a cmd file, follow some prompts, and you should be good to go.
Let me know if you have any questions
Doug