Is your problem with a normal or URL Shortcut as I have had the same issue on a RM CC4 Network (XP & WIN7), when trying to add a URL Shortcut.
Tried various solutions with no success, but in the end resolved the issue by creating a normal shortcut to internet explorer + website (e.g. "C:\program files\internet explorer\iexplore.exe" Scratch - Imagine, Program, Share). This woks fine and appears in the relevant assigned program set.
Hope this helps