Hmm sure sounds like a rights problem.
If the tape drive was on the Exchange server, I'd suggest trying to backup Exchange using NTBackup, but that won't work across a network.
If you logon to the media server as the BackupExec service account and run ExchangeAdmin can you access everything?
Just for grins, setup a new ID in AD and make that ID an Exchange Admin, then from the Backup Selection screen, right click on the Exchange Store and select "attach as" and give it the new ID. Then try another Exchange backup