Problem starting .exe programs

I have a W95 computer that was hit with the Navidad virus last week. I have run through all the ‘cleanup’ of it but now when I try to start any program with an .exe, it comes up stating ‘Windows cannot find .exe This program is needed for opening files of type Appliction’ it then asks for the location of .exe. I look under FILE TYPES and for Application it says Control Type (MIME): application/x-msdownload and for Opens With: Command.
All signs of the virus seem to be gone, just cannot openany .exe files. Looked at 2 anti-virus sights and neather say anything about this situation.