1) Make sure you have some Anti-Virus software--preferably something well known like Norton or MacAfee--installed and updated with the latest virus definitions.
2) Start up your system in Safe Mode.
3) Turn off all Services you don't absolutely need or don't recognize.
4) Remove any program startup selections you don't absolutely feel safe with.
HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Run
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Run
5) Run a full virus scan on your system.
I did this and found that a number of the services that had been installed were infected. I then removed those services using Add/Remove Programs and found they were not removed--surprise, surprise. So I removed them from the disk, manually, and then removed all references to them in the registry.
This is a hassle, true, and if you have backups of your data and know its virus free, might be easier to reinstall windows. I found this to be an easier solution, though, and it worked.
Good luck.