Depois de bater minha cabeça contra isso por vários dias, eu acho que finalmente encontrei o molho secreto.
Originalmente, eu estava obtendo minhas configurações de DNS do meu roteador (configurado para usar o OpenDNS em vez dos meus ISPs - 208.67.222.222 e 208.67.220.220).
Este é o resultado em /etc/resovl.conf
# Generated by NetworkManager
domain Belkin
search Belkin
nameserver 192.168.2.1
nameserver 208.67.222.222
nameserver 208.67.220.220
Não tenho certeza se isso é correto ou típico, mas decidi cortar o roteador completamente fora do loop. Alterei minhas configurações de IPV4 para minha interface de rede de Automatic (DHCP)
para Automatic (DHCP) addresses only
e configurei meus servidores DNS para 208.67.222.222, 208.67.220.220
Depois de reiniciar o computador, é isso que eu recebo no /etc/resolv.conf (NOTA: desabilitar e reativar a interface também atualizou o resolv.conf, mas não resolveu o problema)
# Generated by NetworkManager
nameserver 208.67.222.222
nameserver 208.67.220.220
Com o reinício, tudo parece funcionar bem agora.
Só para verificar, redefini minha interface de rede para Automatic (DHCP)
e fiz o ciclo (desativado / ativado). Meus problemas de DNS foram reiniciados imediatamente. Um segundo loop através do procedimento tem tudo funcionando novamente.