I would try to run one of the virus checkers in DOS, like F-prot. I have had many problems dealing with virii lately on client's computers where they will get them from email or what not and it keeps reinfecting itself upon booting into windows. Either work in Safe Mode or go to dos and use a good anti-virus program. Installing one after you are infected is too late cause the virus will corrupt the antivirus program. If you have an antivirus program previously installed, make sure it is up to date at least once or twice every two weeks. If you have the Klez virus, you might have the Elkern virus as well. Some checkers will not find some virii or you will have to manually delete files if they can not be disinfected.
I cleaned off my boss' home computers and found the klez, Elkern.c, and Kriz virii on it this time. The Klez would reinfect itself if you tried to clean it from windows so you need something to clean the memory and to be able to clean it from the windows files that are open when Windows is run so I did it in DOS (more difficult to do in NT systems). You will probably have to edit the Registry as well to get the virii completely off the machine. Everything seemed fine after reinstalls and then several scans, and then I reinstalled NAV after finding it had the rescue disks and liveupdate was corrupted with the virii, and it found two more virii after running another scan overnight. This time they had the HLLW.Acebo and the HLLW.Bymer virii.
Hehe You can't imagine how irritating it is to keep finding different virii all the time on systems that have been "supposedly" clean. On one of their old machines downstairs I was asked to clean off this one virus and found 5 others on the machine at the same time. I have only had virii two times on my own machines in the past, one was due to carelessness in downloading and not checking my download, and the other was from backing up a friend's machine onto my own before scanning it for virii.
If all else fails, and sometimes this is the best solution, you can always reformat and reinstall. If enough programs are corrupted then you'll have to reinstall anyway. In any case, make sure that you aren't infected first cause as they say, the klez will spoof, but I'm not sure which or if all strains will do this.
Symantec has some good info on cleaning specific virii from your machine if you go to the site and search on the specific virus. You can also go to several anti-virus sites to do an online and limited scan of your computer to see as well if you are infected.