Active Directory could not create the NTDS Settings object for this domain controller

I am working in an organization that is right now running a Windows 2000 AD domain. All the domain controllers are running Windows 2000 with SP4 and have all of the most recent updates installed. Recently, I was trying to promote a Windows 2003 member server to a domain controller, however I was presented with the below error message after clicking next on the summary within the active directory installation wizard:

The operation failed because:

Active Directory could not create the NTDS Settings object for this domain controller CN=NTDS Settings,CN=M1 FSRV,CN=Servers,CN=DomainnameHeadOffice,CN=Sites,CN=Configuration,DC=domainname,DC=co,DC=za on the remote domain controller M15 EXCH.domainname.co.za. Ensure the provided network credentials have sufficient permissions.

"An attempt was made to modify an object to include an attribute that is not legal for its class."

Any ideas?

Can you check your configurations for DNS, point the NIC primary DNS to a existing DC/DNS server, Also check if Active Directory Sites and Services, do you see any server listed there with the same name? Check permissions and FW ports and although this isnt necessary, but if you add the server to the domain and then promote it to a DC.