Does the new media show up in Devices as being recognised by Backup Exec when the job runs?
Personally I've found that on some of the systems I manage, Backup Exec just seems to pick up the fact that a new tape has been inserted and goes ahead and uses it correctly, while on others it doesn't. I don't know if there is a proper reason for this, or simply an error in the way I've set them up.
The easiest way I found to get around this was to use the Backup Exec command line applet, which can be found in (assuming default path) c:\program files\veritas\backup exec\nt\bemcmd.exe. If you run bemcmd.exe -? you'll get a list of all the switches etc, but the ones you would be after would be either -o103 to inventory a robotic library, or -o117 for a stand-alone drive.
So for instance you'd have :
bemcmd.exe -o103 -a"HP 1" -s1,2,3,4,5,6 (for a 6 slot loader)
or
bemcmd.exe -o117 -d"HP 1" (for a single drive)
where HP 1 is the name of the drive as listed in Devices.
Personally I put it into a batchscript which is then scheduled to run 10 minutes before the backup starts, but that's mainly just because I like batchscripts. You could also run it as a Pre-command through the job properties.
Keith