If you look at the properties of the shortcut can you see them? Is it a permissions problem maybe?
It could also be the shortcut isn't relevant for the desktop that it is run from, if you can open the shortcut properties can you open the file location?
cheers
Andy