NT Server 4.0, SP 6a; Backup Exec version 7.3 build 2575 with Exchange agent

Just upgraded to the above mentioned version. I try to perform a backup
and the job gets stuck in the "Loading Media" state and ejects the tape after
a minute or two. Why is this happening and what can be done to resolve the
issue?