Your details are a little sketchy. Are the workstations and server on the same logical network? Can they ping with no problems? Is there anything in the error logs of the router or the systems? Are these systems part of a microsoft domain with the server as domain controller? How are you using VPNs? To me this sounds like something is timing out.
You might want to test connectivity by putting a workstation and the server on a small switch together and see if there are still problems.