Graças a @meccoooll, encontrei uma solução para o meu problema:
Acontece que resolv.conf
foi um symink para si mesmo . Eu nunca vi nada assim e eu não sei como isso poderia acontecer, mas aconteceu em uma nova instalação do Ubuntu 16.04.
A correção é simples, execute
# rm /etc/resolv.conf
# ln -s /run/resolvconf/resolv.conf /etc/resolv.conf