There's nothing in the "old domain" that can't be fixed. Further, I'd state that there's nothing that can't be fixed while the "old domain" is still in production and being used for day-to-day business. I'd go even further out on a limb and say that, so long as you have someone with reasonably good Active Directory knowledge helping you out with the cleanup work, there's very little that can't be done to clean up the "old domain" that would require the users to "notice" that something was being done.
Changing out the entire domain is going to be very difficult not decidedly Not FunTM, what w/ workstation trust relationships, domain account SIDs being named in user profiles, and re-creating all your group policy objects and filesystem permissions. Don't do it. You can fix what you already have, and even if you have to contract with somebody to help you you're probably not going to spend the money that it would cost, assuming this is a network of any size, to change out the domain.
Edit:
Ohh-- you're the dude with the missing RID 500 BUILTIN\Administrator account in the domain. I didn't see that when I first wrote this. Like I said in the answer to your question about that, get on the phone w/ Microsoft PSS. They can probably get you out of the jam. In fact, I don't imagine that anyone else can help you anyway. To my knowledge it's going to take very low-level access to the AD database to re-create that account.