Why don't you generate new shortcuts by right-clicking the associated file (for example: Microsoft Word.exe), and then clicking Create Shortcut. You can then move the new shortcut to the appropriate folder (for example, C:\Documents and Settings\profilename\Start Menu\Programs\Microsoft Office). You could then rename the shortcut to "New Office Document" or whatever you want.
j/k
edit Ooops didn't look @ the date...