My first attempt would be to try and reinstall the software again and then try uninstalling. Sometimes the first failed uninstall attempt has removed files that are needed for a successful uninstall and the only way to fix the problem is to reinstall the application. Other than that it may mean manually removing the program from the registry which is tricky and dangerous if you don't know what you are doing.
Before you attempt a registry removal backup the registry. This tool will backup the registry for you.
If you think you are infected submit a hijackthis log here.How to submit a hijackthis logDownload Hijackthis
Try running the following from safe mode (Getting to safe-mode
you'll also need the virus template file from here
Also try installing and running A2 Free
I'd also run Spybot
If your using Win2K/XP run adaware/spybot from "safe mode with command prompt"
At the C:\ prompt type the following:-
C:\progra~1\spybot~1\spybotsd.exe /autocheck /autofix