If you are receiving a message from some program that your computer is
infected, that "some program" is the malware. Since you didn't give any
details - important ones, like the name of the program giving you the
message - I can't give you focused help. You could have a variant of
Smitfraud, Vundo, Zlob, etc.
Start by seeing if there are removal steps for the program giving you
the message here:
If not or you can't find anything on Bleeping Computer, either go
through the following general malware removal steps yourself, post on
Bleeping Computer's forums, or have a computer professional clean up
The site is in German but David's tool is in English so don't let that
worry you. Scroll all the way down to almost the bottom of the page and
you'll see a box titled "Infos Zum Download - Multi-AV Scanning Tool".
You'll see "Download von www pctipp.ch" and the live link to download
When all else fails, run HijackThis and post your log in one of the
specialty forums listed at the first link above (not here, please).
Not all tools used will work in Vista and you will need to run them
elevated. If you are unable to remove the infection by following the
general steps, register at one of the HijackThis forums as suggested.
Standard disclaimer: I can't see and test your computer myself, so these
are just suggestions based on many years of being a professional
computer tech; suggestions based on what you've written. You should not
take my suggestions as a definitive diagnosis. If you can't do the work
yourself (and there is no shame in admitting this isn't your cup of
tea), take the machine to a professional computer repair shop (not your
local equivalent of BigComputerStore/GeekSquad). Please be aware that
not all local shops are skilled at removing malware and even if they
are, your computer may be so infested that Windows will need to be
clean-installed. If possible, have all your data backed up before you
take the machine into a shop.