Resolvconf -u gives the error "resolvconf: Error: /etc/resolv.conf must be a symlink"

It's easy to fix. Just open a terminal and run the following commands:

sudo rm /etc/resolv.conf
sudo ln -s ../run/resolvconf/resolv.conf /etc/resolv.conf
sudo resolvconf -u

As of Ubuntu 12.04 resolvconf is part of the base system. You can recreate the needed symlink by running

dpkg-reconfigure resolvconf

or by doing the following in a terminal.

sudo ln -nsf ../run/resolvconf/resolv.conf /etc/resolv.conf

Note that as of Ubuntu 12.10 resolvconf no longer aborts if /etc/resolv.conf is not a symlink. It does print a warning message, but this can be silenced by putting the line

REPORT_ABSENT_SYMLINK=no

in /etc/default/resolvconf.