You may need to run the backup/restore using an account with the Send As and Recieve As permissions. By default the administrator does not have these on the Mailbox Store.
Here's how to get around it: Make a new group, called Backup Exec, as an example, and add the administrator, or any other admin users you want to it.
Open up Exchange System Manager and locate the Mailbox Store. (Servers -> [Server] ->First Storage Group -> Mailbox Store)
Right click it and go to Properties then click the security tab. Add the group "Backup Exec". Give that group full control.
This also gives the administrator and any other users in that group total control over everyones mailboxes. ie, they can open them in Outlook and view all mailbox items.
Try the backup/restore now. Good Luck.