Eso fue justamente lo que me acaba de suceder. Hice el upgrade de uno de mis servidores DNS Etch a Lenny, en un primer momento todo pareció haber salido bien sin problemas, es más me sorprendió que nadie se hubiera quejado. Sin embargo tras 30 minutos de aplicado los cambios una llamada diciendo que tenía intermitencias en el servicio me llevo a revisar nuevamente el server que había actualizado.

Aparentemente todo funcionaba bien en el server, pero si se intentaba enviar un query usando nslookup desde una máquina diferente al server para todo dominio que no estuviera delegado a dicho server restornaba que no podía resolver el dominio. Me tomo como 20 minutos dar con una página web donde daban la solución al problema. Todo el problema es que por defecto en Lenny la recursión en bind9 está deshabilitada para cualquier máquina que no sea el localhost y todo el truco esta en añadir estas líneas al archivo /etc/bind/named.conf.options:

recursion yes;
allow-recursion {any;};
allow-query {any;};
allow-transfer {"none"; };

Espero que esto le ayude tambien a aquel que haya tropezado con este problemita.