It may be worth running another anti-virus programme, as not all of them pick up on everything. AVG and Avast! both have versions you can download for free. If you can't access their pages, download the software onto a memory stick using another computer, and then try installing it on your infected machine. Make sure that you don't transmit any viruses to other machines via your memory stick though! If the programme isn't technically a virus, however, but something like a piece of malware, you might like to try something like Ad-Aware (also available for free).
Regular backing up is a good idea anyway, but I'd try to see if you can remove it before having to go down the factory settings route, as that could cause you all manner of other annoyances.