I've similar problem, but is appears to only be Microsoft programs
(how ironic). Office 2007 won't launch from the START MENU, but if I
go into the ALL PROGRAMS and select the components from the Microsoft
Office folder menu they start.

Now a new piece of Info, I just installed a fresh version of MapPoint
2006, and I get the same behavior. Another Microsoft product that
does not launch from the Start Menu.

(Note, I have had to put the Office icons in the Quicklaunch bar to
quickly get them running).

Ideas?