I run both Ad-Aware AND Spy-Bot, as they both seem to clean different corners. I had a similar problem about a year ago, and after booting in Safe Mode, disconnecting my internet connection, running both spyware programs, my anti-virus full scan (NAV 2004 at the time), then doing a reboot, it seemed to get along just fine. I got all of those updated as soon as I could get back on the internet, and ran them all again, just to be sure.
Hope it works for you!