Server2003 Domain Admin account password

Here is a quick overview:
I have a server which had a rogue “IT worker” who changed all domain account passwords, including the domain administrator account.

I can log on as the Machine administrator with all machine level privaledges, however the domain is locked to me. Any suggestions regarding my best course of action? I am considering blowing off the domain and re-creating it from old backups, but if anyone has any “quicker” suggestions, I am all ears.

PS. this IT person is no longer under contract 😉