Okay so there's only one domain, my next question is, was Exchange 2000 upgrade focussed on the schema master. For each domain forest there can only be one schema master and this is the only machine on which the schema can be altered. Is it possible that the upgrade was done on a machine which had been isolated from the network and if so is it possible that someone told it to seize the schema master role?.
The way to find out which machine has Schema master role is to launch an MMC and addthe schema console, right click the active directory schema and choose operations master.
It's possible that there is a schema master in the domain and that the machine on which Exchange was first installed also thinks that it is now a schema masters.
If this is the problem, the answer may be to reinstall Exchange 2000 on the schema master itself. This machine does not need to be in constant contact with the domain, so it could be done offline. I don't know but I would suspect you wouldneed to take out and reinstall active directory on the domain controller on which the first attempt to upgrade took place.