You hadn’t mentioned it specifically, but it sounds like you might have another domain controller in the AD. If this is true you can do the following without have to completely reinstall:
1) Seize all of the FSMO roles on the other domain controller
2) run DCPROMO /FORCEDEMOTION on the ailing domain controller
3) Remove any orphaned objects in the AD on the good DC.
4) Reboot the ailing DC
5) Use DCPROMO to build the AD back up on the machine.
6) Move the FSMO roles to the new domain if you like
Of course, if my initial assumption is wrong and you do not have another DC – then you will have to rebuild the DC and restore from tape.