You could just try the shortcuts, c:\Documents and Settings\*userid*\Start Menu
Look in there, see if you can launch the program while logged on as the person who can't see it in their Start Menu. If it works, then just copy that link and paste into the same area in your own Start Menu folder.