viking12344,
I just finished doing the exact same thing on a clients machine on thursday
Here is what I did:
Download the latest ad aware and update
Download HIjackthis and run it, that prog works wonders.
In additon delet temp, temp internet, mru's recent, ect....
As i reread your post I see you have resolved the issue, cool!
I would reccomend that if you work on systems you will see this again, many many times, Hijack this is a good tech tool to have.
Laterz,
dafanman