slodave
I have seen this on some AD environments that I have worked on.
Do you have only 1 DC in this domain? If you have 2 than you can point DC1 primary DNS settings to DC2 and vise versa.
Have you run netdiag to see if you get a failure?
Of course it sounds like you may have found your problem.
Clay Perrine
5 years of MS AD support- do you have any hair left?
If you point it to itself I think you may get the same errors in the log, since when the DC is booting up AD may not be fully initialized (depending on what else is starting up on the DC).
Just a thought.
Rob