We have a file server running Windows 2003 Server which has several folder shares. When I have to shut down the file server for maintenance, I have to reboot every single workstation as their shortcuts don't work after the file server is rebooted.
Are the shortcuts pointing to a UNC path or a network drive mapped on the workstation? There seems to be a problem with network drives not refreshing themselves automatically. If it's an UNC path, I'd see if file server's IP changes after a reboot, maybe its a dns cache issue.