hi,
you can try this just to rule out if it's BE or something else.
You can't get access to those mailboxes with the Exchange Administrator because by default it doesn't have access to mailboxes.
Go to this link and create this account:
http://support.microsoft.com/?id=292509
It is the exmerge account. It will have administrative rights on your server as well as full access to all mailboxes in your exchange server.
Use that account for the Backup Exec credential.
At the very least if it doesn't work you know it's not a credential issue and something else is happening with your BE.
Hope this helps
---Cheers
shirmal