Try these 'network' troubleshooting ideas:
1. Try to connect by IP if you are connecting by 'name' now.
2. Ping the IP and hte name to ensure both are returning in sufficient time.
3. Connect from a machine on teh same subnet and record results.
4. Add an entry (temporarily) to the host file representing your server and retest.
In my experience, these type of things had to do with the wrong DNS entries on the clients with a problem. Not saying thats the only case, but it is one I've seen in the past.