was the exchange server also sole, um, domain controller and you rebuilt the domain maybe? just guessing.
could this be you? excerpted from 823176 support.microsoft.com
Method 3: Restore a Mailbox from Backup to a Recovery Server
Use this method if the mailbox object in the recovery storage group cannot be matched to a user object in Active Directory that has the same msExchMailboxGUID value. This situation may occur if the user account is deleted from Active Directory or if the Exchange attributes are removed from the user account, and the mailbox in the Exchange store was not reconnected or was purged.
To recover a mailbox from backup, you must have a recovery server that has sufficient storage capacity to install Exchange Server 2003 and to restore the private information store database. This server can be on the same physical network as your production Exchange Server 2003 computer.
To restore a mailbox from a backup to a recovery server:
Make a note of the following information that is on the production Exchange Server 2003 computer:
Organization name
Administrative group name
Storage group name
Install Windows 2000 Server or Windows Server 2003 on the recovery server, and then create a new Active Directory forest.
Run Exchange Server 2003 Setup, and then create a new organization that uses the same name as your existing Exchange organization.
Do one of the following, as appropriate to your situation:
If the name of your administrative group is First Administrative Group, go to step 6.