I had the same problem a week or so ago... try this site:
http://filext.com/faq/broken_exe_association.php
Don’t know what point you’re at with all the advice been thrown at you. I visited a forum where the virus was placed in a banner ad (Java exploit). It mimicked my AVG panel and while I thought I quarantined it, I actually loaded it. Once I got rid of the virus I wasn’t able to run and .exe file. I got regedit.exe to run by copying it to regedit.com.
I am going to try a utility to fix that, it also makes a registry backup just in case.