HI jabba,
both Backup Exec Media Server and Remote Agent should be same version.You can install Remote Agents, from media server. I guess every Remote Agent needs a license.
I do not understand the error "Access to a device was not authorized" what this means? What means device?
Can you run a backup only to the media server?
What happens when you run a backup only to a remote server.
Another good practice is to run Symantec LiveUpdate, may be you have a hotfix that solves your issue.
Regards,
JoaoMatos