Try this, it may be a place to start:
http://www.dnsreport.com/
Then go to your dos prompt on your computer and do a tracert to your server, tell your clients to do the same to see where the problem is if it connectivity.
run:
cmd
tracert xx.x.xxx. (your ip)
Even if your host is giving you gigs and gigs of space your first partition may only be a portion of your total space on the server. When it hits the limit in the 1st 2nd 3rd partition, harddrive, it is rarely a seemless transition. Most of the time the tech needs to tweak it.
Make sure your logs are resetting. If they get too big and don't turn over it always make the server run like shit.
Maybe you are just getting hella traffic???
