Are you SURE you are using HP tapes???
It has been known to happen that unreputable disk/tape houses counterfit
HP lables and such, and place them on low quality tapes. I am obviously
not saying that this has happened to you, but the symptoms sure point to
the tapes.
David