It probably an issue with the configuration of the DNS server. Check with that before... also are you using your own cache or...?

Check opendns.com, it will help!