MAPI error: 80040113 and 8803-94-23-80040113 when running the Migrate Users wizard (4249168)

When attempting to migrate messages, the wizard gets to the point of selecting the Exchange server and then the following error is reported:

Unable to open server "exchnageservername" MAPILogonEX(Profilename)
Error 80040113
[8803-94-23-80040113]

This error can be caused due to the information store or storage group not being accessible to Notes Migrator.

Customers have reported that by moving the migration account mailbox to a different storage group or store has resolved the issue.

For further troubleshooting steps, please see below:

1. Create a new outlook profile and type in the servername and account as seen in the NME wizard. Turn off cached mode, and click "Check Names". This should also fail.
2. Open up the migration profile in outlook and add another mailbox on the same store where the migration account is located. This should allow you to traverse through the folder structure of the other account without any errors.