We have (had) the same problem. It was (temporaraly) resolved by recreating the queue and the job. (default solution from CA)
Later on another server we have a simular problem:
This server just has 1 SDLT drive and the job starts normaly. But after 35 minutes the job start again (not another job,but the same job). It kills the current backupjob and restarts, trying to format the tape but is unable to because it is already formatted and part of the save set.
I am still waiting for an answer and solution from CA
Greets