This is for rbeachler. If you're having problems with brand new tapes, you need to format them. Either use a different server/drive or use the ones you would normally for Backup Exec, but stop the BE services when nothing else is running.
I'm guessing you're using NT? If not, forget the rest of this post!
Then, you need to run NTBACKUP /NOPOLL from an NT Command Prompt.
Use Operations | Hardware Setup and select the necessary drive according to the SCSI IDs (If you don't know and you're using an array, fill all the drives with new tapes and label them up for the future!) Make sure that any valid data tapes are removed first!!
Select Erase Tape and confirm. (The /NOPOLL switch bypasses checking the tape first, it just goes and does it.)
Once you've prepared all your brand new tapes, they should work when you use them in Backup Exec.
Remember to restart the BE services if you stopped them in the steps before.
Also, you can use Veritas Raidirector (if using v8.5 or 8.6) to erase tapes which is very quick and you don't need to stop the BE services!
Good luck and I hope this works for you.
Sparkler.