Event ID : 40960 LSAsrv / SPNego

I’m running Windows 2003 Server DC with Service Pack 1. Recently I created an AD domain in the forest, but whenever I restart the DC I use to get an error message in the root DC of this Forest which as follows:

Event ID : 40960 LSAsrv / SPNego
The Security System detected an authentication error for the server ldap/mrkdc1.test.com. The failure code from authentication protocol Kerberos was "There are currently no logon servers available to service the logon request.
(0xc000005e)".

Event ID : 40960 LSAsrv / SPNego
The Security System detected an authentication error for the server LDAP/MRKDC1. The failure code from authentication protocol Kerberos was "There are currently no logon servers available to service the logon request.
(0xc000005e)".

Event ID : 1059 DHCPserver
The DHCP service failed to see a directory server for authorization.

Can anyone please help me out?

Anyways, seems like I fixed the problem myself. While troubleshooting I just demoted the child DC and everything got fixed. Now there is no more errors.

But I would like to know what was causing the error? Any idea?

Most probably there would be any service running in the background which would be trying to authenticate before the DC starts properly. Anyways, Microsoft has knowledge base articles describing the same. You can check out here:

Event IDs 40960 and 40961 in the System Event Log When You Restart Windows Server 2003 After You Run Dcpromo.exe http://support.microsoft.com/kb/823712/en-us

LSASRV Event IDs 40960 and 40961 When You Promote a Server to a Domain Controller Role http://support.microsoft.com/kb/824217/en-us

Have you reviewed in your firewalls the dropped and rejected traffic?
Surely all rpc dynamic ports are denied from 1024 to 65535.
I had the same problem and I had to add this rule between dc on both domain of the trust and also between a web server where the trusted accounts have to logon.
IF you want to use fixed tcp ports to avoid open the whole range, read this KB article:
http://support.microsoft.com/kb/224196