I was having the same problem. I logged into the server, tried host
www.webmin.com worked fine. /etc/resolv.conf was corretly pointing at good DNS servers (my Host's). Same problem through webmin interface. I updated my /etc/hosts file. Still the same problem.
Then I simply started BIND. It had not been running. As I said, my hosting company was doing DNS for me. I started BIND and *poof* it worked. Maybe that will help someone. Turn on BIND w/ WebMin and it might help.