Windows 2003 R2 x64 DC taking Long boot time

I have just added a new DC (win2k3 R2 x64) to my Windows 2000 domain.
The Server takes an extremely long time to Boot up. The server will first hang quite a while at the "preparing network connections" prompt, and then again at the "applying computer settings"
prompt.  It will eventually bring up the login prompt and allow me to log in, but once in, I can see a number of alerts in both the Application and System Event Logs.

One of the first errors I see in the Event Log is this:

Event Type:      Warning
Event Source:      LSASRV
Event Category:      SPNEGO (Negotiator)
Event ID:      40960
Date:            6/2/2008
Time:            9:48:30 AM
User:            N/A
Computer:      ARMUK-DC0
Description:
The Security System detected an authentication error for the server LDAP/Localhost.  The failure code from authentication protocol Kerberos was "There are currently no logon servers available to service the logon request.
 (0xc000005e)".

For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.

Also This

Event Type:      Warning
Event Source:      NETLOGON
Event Category:      None
Event ID:      3096
Date:            6/2/2008
Time:            9:41:21 AM
User:            N/A
Computer:      ARMUK-DC0
Description:
The primary Domain Controller for this domain could not be located.

For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.

This server doesn't hold any FSMO roles yet as I am concerned that once I move them over I will have the same problem to long boot times, and it just doesn't seem reliable.

Any ideas would be appreciated.

Thanks

Arm