Ran into a similar problem with Veritas version 8.
Tape like other magnetic media has a point at which it will no longer function properly because the surface wears down due to repeated use.
Try doing a quick erase on the tapes once you have them swapped out. That worked for me. When we upgraded to a newer version of Veritas(12) we had to do an inventory then a quick erase to get the tapes to function properly. We established a tape replacement program and have found that we no longer have to do the inventory and quick erase to have the backups run properly. Please let me know if this works for you.