Check whether your regedit executable is still present, and check the properties to verify that it is in fact regedit. Then if double clicking doesn't work on it, use your task manager to check running processes for strange processes. You can use Sysinternals Process Explorer to find out more about what's going on in your system.

After removing the malware, if the problem still persists, chances are the thing has corrupted your default registry settings. You'll need to do some advanced googling for it; it involves resetting the hidden and superhidden keys to default values in both HKCU and HKLM.