All of the tapes are 20GB/40GB 4mm tapes. I would agree that it sounds that the tape is full if it weren't happening at such odd intervals, and inserting another tape has no impact. We have a stock of 11 tapes that we rotate, and it is not obviously certain tapes that are posing the problem.
We I have downloaded and installed every update that was listed on Veritas' site, but I don't know that I have every driver update. I have all Windows updates installed. I will check Dell's site to see if I have hardware driver updates available - but could that be a problem sometimes and not others? For instance, the backup was completed 100% last night (with 23G backed up).
Our backup runs each week night (so 5 tapes/week). The first problem was 4/13, then 4/22, 4/27, 5/2, 5/9, 5/11, 5/16, 5/19, 5/24.