The subject behavior will occur if the RID Master FSMO  role holders is not available, or fails to replicate. The domain controller can't obtain and initialize the RID pool.

This behavior can also be caused if the Access this computer from the network User Right has NOT been granted to the appropriate groups, like Authenticated Users and/or Enterprise Domain Controllers.

To resolve this issue:

Check the Directory Service event log for additional details about replication failure.

See the following Microsoft Knowledge Base articles:

How to Find FSMO Role Holders (Servers).

How to Troubleshoot Basic TCP/IP Problems in Windows NT 4.0.

Using NSlookup.exe.

If the RID Master FSMO role holder is down for an extended period, see Flexible Single Master Operation Transfer and Seizure Process.

To add the Authenticated Users or Enterprise Domain Controllers groups to the Access this computer from the network User Right:

1. Open the Domain Controller Security Policy from the Administrative Tools folder.

2. Navigate through Security Settings / Local Policies / User Rights Assignment.

3. Double click the Access this computer from the network User Right and Add the missing group(s).

4. Open a CMD prompt and type:

secedit /refreshpolicy machine_policy /enforce