What Smi said - there's a new free AV available, AntiVir which might be better than AVG.
Also make sure Windows is patched and you've got the firewall enabled - or disconnect the computer whilst you try and clean it just to be sure.
Reformatting and re-installing everything could be just as much, or more, of a pain as uninfecting, so try to clean your machine before you start over.
Oh and Safemode is your friend.