Windows refusing to run cmd.exe, regedit and batch files

The shortcuts for my backup software don't work any more. Windows says it can't find the batch file listed by full path in the shortcut, but the batch file is there, with no strange permissions. (This is on a colleague's computer. His user account is an administrator.)

So I tried to run a command prompt. Did START->Run->cmd and got the message:
"Windows cannot find 'cmd'. Make sure you typed the name correctly, and then try again. To search for a file, click the Start button, and then click Search."

I looked in C:\Windows\System32, and there it was, cmd.exe, file version 5.1.2600,2180, so I double-clicked the icon for cmd.exe, and got this message:
Windows cannot find 'C:\WINDOWS\system32\cmd.exe'. Make sure ...

I copied this file to another name, cmd2.exe, in a different folder, and it works perfectly. Now I have a copy in \Windows\system32 that works perfectly also.

I wanted to check the registry to see if
HKCU\Software\Policies\Microsoft\Windows\System\DisableCMD
had been set, but regedit couldn't be found.
Copied it to RegEdit2.exe in another folder, and it works perfectly. Searched the registry for DisableCMD, but the key doesn't exist.

Antivirus running is AVG corporate, last updated June 20, 2008, last complete scan June 21, 2008.

I asked Google, and found EE item ID: 20547191, which is the same problem. I worked through the suggestions there, without success, namely:

Did START->Run sfc /scannow
This started the monitor window, and took 50 minutes to scan. No report of any system files repaired.

Did burrcm's suggestion, renamed cmd.exe to xcmd.exe, but the system didn't notice, even when I ran sfc /scannow again.

Took Milan Ojh's suggestion and ranamed Config.nt, Autoexec.nt and Command.com with an x at the beginning of each one's name (but it seems strange that that would cause the problem, because it seems to me they are things that would be used after cmd.exe starts running.) Ran sfc /scannow again, but it didn't replace them.

Tried the suggestion from and235100, to copy a cmd.exe from Line 228 "Restore CMD.EXE" at
http://www.kellys-korner-xp.com/xp_tweaks.htm

This did no good either.

From here on it seems the experts were thinking there wasn't a valid cmd.exe in c:\windows\system32. But there is, and a copy of it by a different name works perfectly.

I've even used My Computer->Properties to modify the environment variable COMSPEC to point to my cmd2.exe, and if I do START->Run and enter %COMSPEC%, it works perfectly.

The PATH variable seems to be set correctly.

So I think something is stopping Windows from "seeing" certain specified programs, even though it can display their filenames and properties. Do any of you know what happens inside the user tries to run a program?

I could send a HijackThis log if you'd like.

Hope someone can help,
   Jim