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

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. (provided by Google) is the easiest to remember.

Add the line nameserver 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 as your primary DNS forever.