Are you using "Connect As" to get to the mailboxes, or just using the BackupExec service account?
If the former, when you log on as the "Connect As" account, can you attach to other mailboxes?
If the latter, when you logon to the media server as the BackupExec service account, can you attach to other Mailboxes?