apt-get cannot connect “failure resolving 'archive.ubuntu.com'”

Just got a new VPS running Ubuntu 11.04 and tried to update it. I got this error. I get the same error whenever using apt-get

login as: root
[email protected]'s password:
Welcome to Ubuntu 11.04 (GNU/Linux 2.6.38-8-generic-pae i686)

 * Documentation:  https://help.ubuntu.com/
Last login: Mon May  7 19:55:45 2012 from 108.192.44.54
root@Rx:~# apt-get update
Err http://security.ubuntu.com natty-security InRelease

Err http://archive.ubuntu.com natty InRelease

Err http://security.ubuntu.com natty-security Release.gpg
  Temporary failure resolving 'security.ubuntu.com'
Err http://archive.ubuntu.com natty-updates InRelease

Err http://archive.ubuntu.com natty Release.gpg
  Temporary failure resolving 'archive.ubuntu.com'
Err http://archive.ubuntu.com natty-updates Release.gpg
  Temporary failure resolving 'archive.ubuntu.com'
Reading package lists... Done
W: Failed to fetch http://archive.ubuntu.com/ubuntu/dists/natty/InRelease

W: Failed to fetch http://archive.ubuntu.com/ubuntu/dists/natty-updates/InRelease

W: Failed to fetch http://security.ubuntu.com/ubuntu/dists/natty-security/InRelease

W: Failed to fetch http://security.ubuntu.com/ubuntu/dists/natty-security/Release.gpg  Temporary failure resolving 'security.ubuntu.com'

W: Failed to fetch http://archive.ubuntu.com/ubuntu/dists/natty/Release.gpg  Temporary failure resolving 'archive.ubuntu.com'

W: Failed to fetch http://archive.ubuntu.com/ubuntu/dists/natty-updates/Release.gpg  Temporary failure resolving 'archive.ubuntu.com'

W: Some index files failed to download. They have been ignored, or old ones used instead.
root@Rx:~#

If needed, here is my /etc/apt/sources.list

root@Rx:/etc# more /etc/apt/sources.list
deb http://archive.ubuntu.com/ubuntu natty main
deb http://archive.ubuntu.com/ubuntu natty-updates main
deb http://security.ubuntu.com/ubuntu natty-security main
deb http://archive.ubuntu.com/ubuntu natty universe
deb http://archive.ubuntu.com/ubuntu natty-updates universe

And if needed, I did a ping test:

root@Rx:~# ping -n 8.8.8.8
PING 8.8.8.8 (8.8.8.8) 56(84) bytes of data.
64 bytes from 8.8.8.8: icmp_req=1 ttl=56 time=13.3 ms
64 bytes from 8.8.8.8: icmp_req=2 ttl=56 time=13.2 ms
64 bytes from 8.8.8.8: icmp_req=3 ttl=56 time=13.4 ms
64 bytes from 8.8.8.8: icmp_req=4 ttl=56 time=13.3 ms
^C
--- 8.8.8.8 ping statistics ---
4 packets transmitted, 4 received, 0% packet loss, time 3005ms
rtt min/avg/max/mdev = 13.243/13.326/13.428/0.066 ms
root@Rx:~#

This is /etc/resolv.conf

root@Rx:~# more /etc/resolv.conf
nameserver 199.193.248.1

The problem is that the DNS server you had originally isn't responding to your queries. You can add another one to the list to check. 8.8.8.8 (provided by Google) is the easiest to remember.

Add the line nameserver 8.8.8.8 to your /etc/resolv.conf to query that server.

If the original server is one that the VPS provider gave you, you may want to bring this up with their support team - it's possible there's some sort of management tool that depends on it. Other than that, you can use 8.8.8.8 as your primary DNS forever.