I would recommend a repair installation. Utilman.exe is a legitimate Windows file, as is cmd.exe, but you can't really shift them in "any way you want". My opinion is, and I would recommend you to wait for other more qualified ones, that you have messed your system, and it would be wise to let Windows decide what to do. Thus, the repair. PLUS a thorough scan of your system.
Everything can be fixed, but it may take time and true expertise. You could try CCleaner, it may be able to fix registry. But the fact that a restore to a week back didn't help, is kind of disturbing.
Quite often problems are faster resolved by a complete re-installation, than by hunting for the actual problem. The advice I always give is, have your hard disk(s)...