I ran into a problem while moving Exchange (2003) mailboxes to a new Exchange (2010) Database :
The solution was to add the Exchange 2010 servers Full Control access (or the Exchange service group!) of the mailbox stores.
(Exchange 2003 System Manager, First Storage Group, Mailbox Store, Properties, Security Tab)
