I already tried lavasoft's "ad-aware." It didn't work. It said I didn't have proper definitions, or some malarchy like that.
Try clicking on check for updates now. And downloading new definitions.
It has always worked for me. Make sure you are downloading it from a reputable site. And after you open it there is a picture on the top you have to click on the get the latest definitions.
In any case...Even without cleaning this stuff off your computer you will notice a huge difference with firefox since a lot of the spyware crap is designed to work only with IE. But not all of it.
http://www.mozilla.org/products/firefox/