You're running DHCP, also, right? I got this exact same error on a 2003 Server I manage. How I fixed it was to configure DNS Dynamic update credentials.
I remember doing it from the command line, but I can't seem to find or remember the commands, so instead, I'm going to point you to the TechNet article I found about it.
TechNet: DNs Dynamic update credentials
Let us know if that works for you.
__________________
I turn away with fear and horror from this lamentable sore of continuous functions without derivatives. --
Charles Hermite
Fakelife.com Nothing to do with archery anymore. Porsche/BMW/Ferrari/Honda videos