ntdsutil auth restore failure

Several questions here before I can give you a better analysis of what is going on:
Is this a domain controller?

Is it the only domain controller in the domain?
If it isn't, unless you are recovering a deleted Active Directory object which has replicated completely through the enviornment, you should be able to recover AD by just using DCPROMO.

How did you backup the System State and SYSVOL?
Just backing up the system state will not fully recover AD. You must backup and restore SYSVOL also.

Did you boot to Directory Services Restore Mode with the right password?
I am assuming that is a yes, but it is always best to ask.

If you have another DC in the enviornment, did you mean to use an authoritative restore?

One of the better papers on Active Directory Recovery is linked here:
http://wm.quest.com/products/recoverymanagerad/

Thanks for the help, here are answers to your questions:
Yes, it is a domain controller. It is the only DC for a Windows 2000 domain but there is an NT4 domain which has a two-way trust relationship with the 2000 domain. I will try recovering AD with DCPROMO and let you know how it went. Both system state and SYSVOL were backed up and restored and the correct password was used to boot into Directory Services Mode.
Thanks for the link to the AD paper, I learned alot from it.

btw I am not sure how this Q&A system works - if I submit an acceptable rating is that the same as replying or do I have to add a comment? Will an acceptable rating close the question?

Thanks

I'll be honest and say I just answer the questions and hope it helps people. The points are secondary to knowing I helped someone out. I think just closing the question usually awards the points.

Since you said that it is the only Windows 2000 DC, DCPROMO isn't going to help you as that only works when you have another Window 2000 DC in the enviornment.

I think this webcast from Microsoft might be a big help in doing your recovery:
http://support.microsoft.com/default.aspx?scid=/servicedesks/webcasts/wc031902/wcblurb031902.asp

And Windows IT Pro has some articles on Active Directory recovery, but I cannot verify how many of the links may still be good:
http://www.windowsitpro.com/Article/ArticleID/22517/22517.html

Another good source is this Microsoft series:
http://www.microsoft.com/technet/community/events/windows2000srv/tnt1-76.mspx

And the TechNet links to AD recovery are here:
http://www.microsoft.com/resources/documentation/Windows/2000/server/reskit/en-us/Default.asp?url=/resources/documentation/windows/2000/server/reskit/en-us/distrib/dsbi_add_mhau.asp

While I am thinking about it tho, the whole issue may be this one. Was this backup done prior to putting Window 2000 SP2 on the box?
http://support.microsoft.com/?kbid=295932

There is also another known issue with mangled names, but that should only happen if there is a Domain Naming Master in the forest. Was this Windows 2000 DC in a single domain forest? Or are you part of a larger AD forest? If so, this could be the issue:
http://support.microsoft.com/default.aspx?scid=kb;en-us;814202

And I am assuming that this is the same hardware you are restoring to and not a different piece for hardware?

Thank you for the response. The backup was done with SP2 on the box, so I don't think it's that. The DC is not part of a larger forest. It will take me a while to look through the other links. The hardware may not be exactly the same as the original server - how likely is it that this is the issue? I have not had problems restoring to diferent hardware before.

Restoring to different hardware does make some small changes, but it can be done. This article covers this exact situation:
http://support.microsoft.com/?id=263532

Long shot:

You may be having junction point problems. AD uses junction points to mark physical locations on the hardisk of the sysvol share and when a backup runs in 2000 it copies these junction points. When restoring you should select the option to NOT restore junction points.

I am in Directory Restore Mode.

I will try the article about restoring to different hardware and I will try not restoring the junctions.

Unfortunately I will not be able to take these steps until 01/12 as I have other responsibilities until then. I will let you know how it goes - Thanks for all the help.

Most welcome sir. Give me a buzz once you are able to look at it again.