if it's in All Users - .. - Program files, it should show up. Is it possible that there are file protections on the link that prevent all users from seeing it? Can you check the file security settings?
Also, are there other links in the same folder and, if so, can all users see them?
Just to triple-check, the directory in question should be C:\Documents and Settings\All Users\Start Menu