We have some troubles moving user from one exchange 2003 to exchange 2007. We found that “Authenticated Users” was not in the user group Users, on the Exchange 2003 machine.
If the Exchange 2003 is a domain controller the Authenticated Users still need to be member of the user group.

The error we was getting was this:
XXX
Failed
Error:
Error was found for XX because: Error occurred in the step: Preparing mailbox to be moved. Failed to copy basic mailbox information with error: The Microsoft Exchange Information Store service could not find the specified object., error code: -1056749241
Exchange Management Shell command attempted:
‘141fc3d8-c100-46e6-b402-fc653b26afe4′ | move-mailbox -TargetDatabase ‘CN=Mailbox Database,CN=First Storage Group,CN=InformationStore,CN=XXXX,CN=Servers,CN=Exchange Administrative Group (XXXXX),CN=Administrative Groups,CN=First Organization,CN=Microsoft Exchange,CN=Services,CN=Configuration,DC=XXXX,DC=net’
Elapsed Time: 00:00:10