Neste momento, tive o mesmo problema em uma instalação recente de 14.10 de 64 bits. Pesquisa rápida na Internet não me dá nada, portanto, decido re-instalar o pacote antes de ir mais longe. Surpreendentemente, a escavação começa a funcionar depois disso.
sudo apt-get install --reinstall dnsutils