Sounds like malware. Have you tried doing the above in safe mode?
Also, can HijackThis run? If it can, please have it perform a scan and put the logs up here.
http://download.cnet.com/Trend-Micro...-10227353.html
I'd go for a full format and reinstall if this doesn't work out. That's pretty entrenched in the OS and it'd be difficult to render it completely clean again.