I see this sometimes on my NAC servers with two NICs. It happens because /etc/network/interfaces has gateway lines for each interface, which causes a hang while the network is being configured, and so the DNS configuration is never set in /etc/resolv.conf. My guess is sometimes dnetconfig has a race condition with this which is why it only works sometimes. I've been meaning to file a bug on this but haven't got around to it.