I have the same problem except it is persistent with every job.
The first time a job runs I get the "Cannot return media to original..." error. The second time I run the job, without doing anything else in between, it works.
This means I can't run scheduled jobs because they fail the first time and I have to run by hand.
I'm using BackupExec 9.1 for NetWare. Any help is greatly appreciated.