dcpromo fails to find Domain Controller

[cmiddl1]

I have a serious issue with the network that I inherited from the previous IT guys. It is a Win2K (SP4 & Hot fixes) domain, with two DC's, both are suppose to be GC's as well. They both have DNS (AD Integrated) running on them, though I have stopped the service on one for now, as well as the Netlogon Service. That is because users were having trouble logging into the domain. Okay, now with that said, I have a new Win2003 server that I wanted to use as a DC (with the possibility that the entire domain goes to Win2003) and when I run the dcpromo app, it fails saying that it cannot find a DC on the domain. The FRS is running, but it says that it cannot replicate the files. There are various DNS, Netlogon and Access Denied messages in the event viewer log. I don't want this to be so long, but can anyone give me some advice as to how to proceed next? Also, when I run the dcdiag utility, it comes back with:

DC Diagnosis

Performing initial setup:
Done gathering initial info.

Doing initial non skippeable tests

Testing server: NYC\DC-01
Starting test: Connectivity
DC-01's server GUID DNS name could not be resolved to an
IP address. Check the DNS server, DHCP, server name, etc
Although the Guid DNS name
(6023ba40-97e2-4995-bad2-747f3d4e9f9e._msdcs.xxxxx-lan.xxxxxxxxxxx.com)

couldn't be resolved, the server name
(dc-01.xxxxx-lan.xxxxxxxxxxx.com) resolved to the IP address
(1xx.x.x.xx) and was pingable. Check that the IP address is
registered correctly with the DNS server.
......................... DC-01 failed test Connectivity

Any answers? I have ideas, just looking for some assistance in fixing this, if possible.