Можно попробовать так:

sudo dpkg-reconfigure resolvconf

Или так:

sudo mv /etc/resolv.conf /run/resolvconf/resolv.conf
sudo ln -s /run/resolvconf/resolv.conf /etc/resolv.conf

Мне помог второй способ.

Еще вариант:

В /etc/NetworkManager/NetworkManager.conf закомментируйте dns=dnsmasq
sudo dpkg-reconfigure resolvconf 
sudo resolvconf --enable-updates