Bem, finalmente consegui descobrir:
Eu alterei a ordem dos provedores de resolução de nomes no nssswitch.conf e estava realizando pesquisas de WINS antes do DNS.
eu mudei:
hosts: files myhostname mdns4_minimal [NOTFOUND=return] wins dns mdns4
Para
hosts: files myhostname mdns4_minimal [NOTFOUND=return] dns mdns4 wins
E minha resolução de DNS está de volta ao normal. O que me impressiona é que esta configuração funcionou perfeitamente bem antes, mas pelo menos o meu problema está resolvido.