I would try a number of things...
First, turn off system restore. I would download >Ad-Aware SE 1.05 and update it. Ad-Aware 1.06 is buggy and lately Lavasoft has been having serious issues with hacking and what not on that version. Also download the V2X add-on. Reboot in 'Safe Mode' and run both AVG and Ad-Aware and it's add-on.
Reboot and see if anything changes. If it does not, I would again reboot in 'Safe Mode' and attempt to delete the files that the error message is showing.
In the event that does not work, I would run an online scan with Panda or Housecall. It will take a while with a 56K, but trust me, it's worth it. I have AVG and it works great, but I found out that it doesn't get everything. I now use AVG, Housecall and I also run NOD32. For some reason, each one of them finds something that the other doesn't. If you're going to use just one...just use NOD32. That's the best anti-virus program out there in my opinion.
If any of that fails for you. I would also download Trojan Remover 1.6.2, and Spybot S & D, but make sure you don't download the beta version as it appears to be a hacked copy. Update those before running. You can get those from Majorgeeks.com or Download.com or a number of other places I'm sure.
Now....if none of that works, then I am worthless to you and it is definitely not a virus or malware.