Consegui corrigir esse problema em minhas máquinas Debian atualizando para o kernel 3.2.0-4 atualmente no Wheezy a partir do 2.6.32-5 atualmente no Squeeze.
Se você não conseguir atualizar o seu kernel, eu consegui contornar esse problema em dois dos meus servidores, dizendo-lhes para acessar o resolvedor DNS local sobre IPv6 em vez de IPv4. Aqui está o meu resolv.conf
:
search example.com
nameserver ::1
Não foi um trabalho perfeito, mas foi suficiente por um tempo.