To avoid jobs to go in a queued state, please verify that the server is not in a paused state. This is one of the main reasons for jobs to be in a queued state.
Refer to the following technotes:
"Device jobs remain in a "pending" or "Queued" state indefinitely; and "scheduled" jobs do not run at their appropriate time"
http://seer.support.veritas.com/docs/191594.htm
Please also check whether the tape meant to store data is over writable.
After following the above mentioned suggestions, please run a test job and see whether it is successful. After that, please run a normal job.
We suggest you to disable the Antivirus software and then perform the backup. This is because the Antivirus software uses the same messaging API as that of the Backup Exec. Also we suggest you to disable any third party software and then perform the backup.
Also verify whether there are any pending alerts. In case there are pending alerts refer to the documents below:
Technote: How to configure VERITAS Backup Exec (tm) to automatically respond to media alerts, including when a backup hangs at 99% until the user responds to a tape eject prompt
URL: http://seer.support.veritas.com/docs/192055.htm
Title: How to configure VERITAS Backup Exec (tm) 9.x for Windows Servers to respond to alerts automatically
URL: http://seer.support.veritas.com/docs/254685.htm