|When you say shortcut are you saying a Mapped Drive or a real short cut? Should do drive mapping instead of shortcuts. |
If it persists then try seeing if it is an DNS issue by using the servers IP address in the UNC pathing as apposed to the FQDN.
\\192.168.1.2\sts$ - or what ever your servers IP is.
If it is a DNS issue then give us a little bit on how you have their local NICs configured and how you are doing DHCP.