Sounds like the swen worm thats been going around recently. I have had a LOT of customers bring in machines infected with this...
anyways, the big problem is that the worm associates it self with exe files (and reg, bat, com, pif.... etc) It also tries to disable the ability to edit registry settings.
If you go to:
http://vil.nai.com/vil/content/v_100662.htm
They have some details on the worm.
To fix the problems this worm created... you will need to download the fixswen.inf file from this page... right click, and choose install.
(Inf files are one of the few things uneffected by the worm, thank god)
Once that is done, you should be able to run executables again (cheer!)... But before you go to far... you need to download something to clean out the remaints of swen. Both Symantec and Network Associates Inc. have tools to do this... and I honestly can't tell you which is better. Synamtec releases individual tools for cleaning each worm, while NAI has a single tool (stinger) which gets updated to clean more and more worms.
Anyways, this should get you going again. =)