I think you're on the right path thinking DNS and Igal's asking some good questions. Check the local hosts logs for RPC errors, if you suspect NetBIOS, try at command prompt:
Prior to forcing master browser, (I'm not 100% behind the idea that's the problem, but you know your network best) check it first with the support tools "browstat"
and you can force an election by restarting the browser service, or using that same tool above:
browstat elect \device\netbt_ieepro1 (your domain name here)
Reading your comment you say that your clients can't see the domain controller, that's a HUGE problem there. They need to be able to see it. Check your SRV records in DNS, and/or on the local node check what the machine/logon sees as the DC. (You can do that by opening a command prompt, typing "set" and dumping the env variables and looking for something that looks like this:
LOGONSERVER=\(your domain controller here)
Try restarting the netlogon service on your DC? (Or probably in your case, just giving it a good reboot wouldn't hurt)