Problem! Please Help!

Hello, I'm kinda new to this site so bear with me...

I was downloading a demo of a game called War Rock when suddenly a pop up appeared, claiming to be installing a trojan horse onto my computer. In panic, I closed the window, canceled the download, and removed all the programs I had used to downlaod it (gamespy, etc), along with other previously donwloaded demos (none of those demos had that problem though.) The next day, my computer was a mess. Everything was running slower, and whenever I went on the internet, random advertisements would pop up in different windows, on sites that never had a pop on them before! Also, whenever I used a search engine like google, the top answers would always be from other search engine sites (ex: bedidle.) I downloaded the AVG free edition, and sure enough, it found a ton of infected trojan files, which it removed (or so I believe.)

Now my computer'r running better, but it still has 3 of the earlier problems: the random ads, the google problem, and the slow runtime. AVG hasn't picked up anything else, and no matter how many times I search, it still can't find the problem. I am at my wits end, and, with a limited knowledge of this kind of thing, I don't know what to do. Can anyone help me with this problem?

Thanks in advance!