Consegui resolvê-lo alterando a ordem inicial em /etc/rc*.d para que o DNS fosse iniciado antes do asterisco.
No entanto, as seguintes atualizações do sistema tiveram a tendência de empurrar de volta a ordem de início original. (Pelo menos eu acho que sim. Consertei, funcionou por uma semana, depois parei de novo.)
Desde que atualizei o sistema para o Ubuntu 10.04, ele simplesmente funciona.