Likely malware - compomised system?

Right, I'll try and keep this brief. I'll do all the scans and things if advised, but I want to find out if my problem is likely to be a malware one first.

I'm running Vista Home 32bit, and I downloaded a file which was masquerading as an mp3, and I'm now sure was a virus. There were no symptoms up until a few days ago, when suddenly I could no longer access gmail.com or some of my other frequented sites. Firefox would give me an error along the lines of "server could not be found". I also tried the sites in Safari, to no success.
Then, some websites stopped displaying images properly, notably bebo.com.
Next, icons and images on my desktop started disappearing. My wallpaper would go black, and files would lose their icons, becoming only a name.

Nothing was picked up during scans, so I backed everything up on DVDs and formatted my computer, re-installing Vista. Everything seemed fine, but not, I'm intermittently forbidden access to Gmail again. I'm now worried that something malignant got backed up and then put back into my system.

After some googling, this page really worried me:
http://ask.metafilter.com/97034/Badware-or-why-I-cant-get-to-Gmail

I don't really have to scrap my computer, do I?
Let me know if I should run the recommended scans, and I will do so.
Any help would be much appreciated.

 

OK, I've done all the READ & RUN ME FIRST scans, and I've attached the logs.

Everything came out clean... Although I couldn't get combofix to run - it said I had an incompatible OS, and that it was only for running in Windows 2000 and XP.

Is there anything visibly wrong?