When you add a new object to Active Directory, you receive:

Cannot create the object because directory service was unable to allocate a relative identifier.

When you use a system state backup to restore a domain controller, the System event log records:

Event Type: Error
Event Source: SAM
Event Category: None
Event ID: 16650
Description: The account-identifier allocator failed to initialize properly. The record data contains the NT error code that caused the failure. Windows will retry the initialization until it succeeds; until that time, account creation will be denied on this Domain Controller. Please look for other SAM event logs that may indicate the exact reason for the failure.

If you run dcdiag /v, you receive errors messages about RID failures.

You may also have System event log entries for event ID 16647 and 16645 that reference RID or 'account identifier'.

To troubleshoot these problems, see Microsoft Knowledge Base article 839879 - Event ID 16650: The account-identifier allocator failed to initialize in Windows 2000 and in Windows Server 2003.