I see where you are at now. You are using 2 different accounts to run backups, one for data and one for exchange. I am using one account dedicated for backups, and this has been set to default logon. So in fact your credentials are working fine, but when it goes to access the mailbox's it tries to use the default account instead of the exchange account.
I'm not sure if you've done this already, but try this.
Go to your exchange selection list, on your left pane you will see "Resource Credentials". You can change the credentials to your exchange logon account, then test the credentials. By default all credentials go to the "system logon account" for the backup server. From here you can set different credentials for different servers on the same selection list.
If you've done that already, then I'm stumped.