sudo: unable to resolve host oldhostname

After changing the hostname in /etc/hostname you might get the following message when sudo'ing:

sudo: unable to resolve host oldhostname

In that case just edit the oldhostname in  /etc/hosts and the error/warning will be gone.