Eu tive o mesmo problema com o Ubuntu 16.04. A dica para resolver isso foi quando eu corri
sudo dhclient
e recebi a seguinte mensagem: /etc/resolvconf/update.d/libc: Aviso: /etc/resolv.conf não é um link simbólico para /run/resolvconf/resolv.conf
Os passos que eu dei depois disso foram: Resolvconf -u dá o erro" resolvconf: Erro: /etc/resolv.conf deve ser um symlink "
Ou seja, executar estas etapas resolveu o problema:
sudo rm /etc/resolv.conf
sudo ln -s /run/resolvconf/resolv.conf /etc/resolv.conf
sudo resolvconf -u
Espero que isso ajude alguém com o mesmo problema.