How odd. And very frustrating.
AT&T never believed me when I had bad DNS juju issues... It didn't get fixed until that major system crash of theirs when whatever was messed up before finally blew up along with the store, I guess.
DNS probs are sometimes the most frustrating at all... mainly because there are thousands of ways for name services to "slightly" fail, and sometimes they're really tough to track down.
Usually though, it's because of traffic. Nameserver gets hammered with too many requests too fast... and start responding erraticallly. Sometimes it works and sometimes it doesn't. And diagnosis tests like PING and TRACERT always work because they are either given a higher priority or are more tolerant of slight delays.
Solution: Buy another stinkin' box. Bigger, better, faster, more. Words to live by.