Windows 7 Explorer.exe incompatibility

On Windows 7 64-bit, the user is getting the following message when Windows logs in:

The program or feature \??\C:\Windows\Explorer.exe cannot start or run due to incompatibility with 64-bit versions of Windows. Please contact the software vendor to ask if a 64-bit Windows compatible version is available

Clicking OK give a blank screen. I can run Task Manager to launch other programs, but I can't run ANYTHING as an Administrator. When I boot off the Windows 7 CD to Repair your Computer, I can open the command prompt and run SFC /scannow /offbootdir=D: /offwindir=D:\Windows (as detected), but it fails and doesn't say what file. I tried to replace the EXPLORER.EXE file with one from my other 64 bit Windows, and the same message appears.

I have tried the KSOD fix of loading the registry remotely and checking the shell registry value, but it's set to Explorer.exe already. I have run CHKDSK /f /r from another computer on it, and from the Command Prompt in the recovery console, no bad sectors found and no repairs to be made. Western Digital Data Lifeguard says the drive checks out fine. Virus scanned on another system, no viruses found.

EDIT: Tried doing System Restore but it keeps failing with error 0x8000ffff. It gets to the Welcome screen with the spinning circle, and that's about it

Figured out the issue (don't think it's fixable though). The registry is corrupt. All the files are there, but when trying to load the SYSTEM hive, nothing appears. So it seems that it's not fixable (CHKDSK didn't do anything, as SFC didn't either) without a reinstall