This could also be a case of virus/malware... One way to check is to go into Safe mode and run the command... Then if it works, go to normal mode and make a copy of the regedit.exe in Windows System32 folder and rename it and try to run it. If it works, this is a possible case... Run AV scan (AVG/Avast are free) and Spyware scan (Lavasoft Adaware and Spybot Search and Destroy are very good, but you should run both) in Safe mode....
Also, post a log of HijackThis so that we can see if there are any strange processes running in your system...
Arun