After upgrading from Windows NT to Windows 2000, even new and clean Win2k servers can develop security rights issues and problems replicating when promoted to domain controllers. Event ID 13508 and 13509 indicate possible issues as DNS lookup failure, DNS service not running, or DCs not all replicated.
The root problem could be that the system root share of your first DC was not fully shared to everyone (the default for C$) when you installed Active Directory. The DCPROMO wizard makes assumptions when setting inherited rights for AD child objects that may not be true (still occurs at SP2). AD copies these settings from the existing DCs when adding new domain controllers and replicates them to the others making matters worse.
Improper object security is the key issue for a host of AD problems. Microsoft is still working on a way for us to set all Active Directory security back to the defaults with one process/procedure.
Check the file share security on the root share, and new shares created by DCPROMO. Also check for sharing of sysvol. After setting share security to match a good DC system on another network or reinstalling the default BASICDC.INF settings in the WINNTSecurityTemplates, enforce the new settings by typing SECEDIT REFRESHPOLICY machine_policy /ENFORCE or reboot. Don't run this on your PDC emulator! It could reset your default Account policies. (Microsoft denies this.) EventID 13516 will be the sign that replication, due to security rights, has been fixed. It may be necessary to delete all the replication connections in Sites and let the KCC recreate them. That should fix this poorly documented but critical problem.