I do have the same problem on all x64 builds of Windows 7: the start menu shortcuts of Office 2007 do not work. I can start all programs directly (by opening the exe files inf C:\Program Files (x86)\...) and I also can open a doc file, for example. When I manually create a shortcut to the exe file, it also works.
It's just the default shortcuts in the start menu (which are created during setup) that don't work. When I open the properties of such a shortcut, the "Target location" field is empty (and can not be edited). The "Target" field says: "Microsoft Office Enterprise 2007". So obviously, the shortcuts were created incorrectly, because they don't contain any path information to the target?