I was getting this when I was doing some test restores yesterday.
If I restored into my own mailbox, and provided my account details, the restore worked.
If I gave myself Full Access to another account in O365 and tried the restore, it failed with insufficient permissions.
Came in this morning and tried again, and the restore worked.
Just tried to restore into yet another mailbox after giving myself Full Access to it, and had the same problem.
Forced a sync with AADC and that didn't help.
About 30 minutes later, it started working.
I think there is just a delay in permissions filtering through the Office 365 Exchange infrastructure. The same delays happen if you assign Full Access and then try to open the other mailbox in Outlook or OWA. You'll get permission errors for around 30 minutes and then it will work.