I've had similar problems in the past when using "imaged" workstations. Even when the computer name and SID's have been changed, shortcuts have embedded UNC information that still points to the original workstation name. If that original workstation name still exists on the network, each time a link is accessed it resolves to the original computer name UNC path, and the normal domain user doesn't have local administrator privaleges necessary to access the c$ share of that original machine.
Two ways to fix this:
1. Find the original computer name and remove it from the network. When the link resolution is attempted, the O/S will first try the original UNC path, if this isn't available a local path will be substituted - permanently. Downside is timeout period required for each different link.
2. If network shortcut resolution isn't a biggie, please follow the information provided in Microsoft's Technet KB article Q158682 to add a Registry value to HKEY_LOCAL_MACHINE subtree. The entry, LinkResolveIgnoreLinkInfo, its value and exact location are fully explained within the article.
Hope this helps, -Ewing