dcpromo fails with AD database failed to initialize

I am trying to promote an existing server to a DC (backup) after it was rebuilt. Before the rebuild, it was a backup DC and also served as a DNS server. It's running Server 2003 R2, just like the primary DC. I run dcpromo and it fails with the error "The Active Directory database failed to initialize (error -1206)..."
In the event log, the event ID is 1168, Source: NTDS General.
Internal error: An Active Directory error has occurred.

Additional Data
Error value (decimal):
-1206
Error value (hex):
fffffb4a
Internal ID:
40826

I'm wondering if the problem is due to the fact that we did not demote it before taking it offline. I have removed any reference to that server from DNS, as far as I know.
Ideas, please?

Please check out once the DNS configuration of the server that you want to downgrade. There must be a first DNS is now the new DC be registered. Once DCPROMO and REBOOT. Alternatively you could with the Resource Kit Tools, an error diagnostic and try to fix it, I must admit, however, make the one that is manually removed much faster as long as it is not a simple error such as wrong netmask not.

I am giving you a link below that has proper information on different error based on event id. This will be helpful for you to fix the problem. There can be some different associated issue. You have to checkout each of them one by one. The following link will help you to find information on first verifying whether AD services are available or not. Sometime due to lack of file the issue appear. The issue also occur due to file permission thing. So just checkout the link and try out different options.

"Directory Services cannot start" error message when you start your Windows-based or SBS-based domain controller

You can try using ADTest tool. This can help you finding out the issue with Active Directory. The tool is available for free. It is also beneficial for testing Active Directory performance issue. There are some more tools you can try out. If you find ADTest a bit limited in terms of usage then you can go ahead with ADBPA. This tool is bit advance and has more things to find out. Through the help of this tools you can locate that is the exact cause. Which file in the system is causing problem.