Right Click on the short cut
Click 'General Tab'
Check the location.
It should be 'C:Documents and Settings\All Users\Desktop'
Refer the picture below
Is there anything wrong with the location?
Refer the next picture. If you find the location something like this in the picture, then copy paste it to 'C:Documents and Settings\All Users\Desktop'
The problem is because of confusion with different user accounts. Check with the user accounts for permanant solution.