I had this issue, and found the root cause, immediate work-around, and long term fix:
Root Cause: if your combined PATH environment variables are more than 2048 characters, then it (and WINDIR) stop being visible in many contexts. This may cause start menu items/programs to be "not found", even though they are in fact there, and work if run manually from
windows explorer or command prompt.
Interim Fix (maybe): I've had mixed results with this, but if you open Task Manager (Ctrl-Alt-Del Task Manager) and quit Explorer (note desktop will go blank and start menu goes away), and then run Explorer again, all the problems temporarily disappear and things work properly. However, this is only a temporary solution.
FIX/Solution: Reduce the PATH variable to be under 2048 characters in total. Using Windows Explorer or via command prompt, run
Click the Environment Variables button at the bottom and review the entries. Deleting unused or not needed entries so the total is under 2048 characters in total (from the PATH variable) should fix the issue. You can then retry the interim fox and all should be well, and once you safely reboot, the solution should stick.
This applies to Windows 7, Vista, XP. Not sure about 8 or 10 yet.