Why was the AVG Anti Rootkit suggested?
Uninstall any search tool bars that aren't from recognised companys like google or yahoo.
Try installing Firefox and use it rather than Internet Explorer.
Also try downloading and running Spybot - Search & Destroy 1.5.1 from here;
http://www.safer-networking.org/en/download/
Follow that up with Ad-aware from here;
http://www.lavasoftusa.com/products/ad_aware_free.php
Each scan should take a while. Be suspicious if either won't run or only take 2 seconds to finish.
If either scan says you need to restart the PC and scan again then do it, but be prepared to have to do some more work to get rid of some nasty infection.
If you go for the nuclear option as suggested by alanworland don't forget to back up your bookmarks/favourites and install Firefox.
Avoid sites that offer free ring tones games and screen savers as many of these will install spyware.
Mark