Try either removing all trace of the old tape drive from within Backup Exec, or installing the replacement tape drive as a completely new drive, so for instance where you may have had the old one installed as HP1, install the new one as HP2.
While the replacement may have been identical a lot of tham have various ID's etc within them which are specific to each drive and which Backup Exec is aware of, so won't properly see it as the same drive (though normally that will cause the drive to go off-line).
Alternatively, the other possibility I've heard of in the past (though not so much recently so newer tapes might not suffer from it), is that when a tape drive gets old the heads can go out of alignment, or become damaged or something, such that the tapes which are used in at the same time are altered at the same time. While that drive and those tapes will work together, trying to use them in a new drive will fail. Might be worth trying some new tapes and seeing if the drive will read them properly or not so you can determine if the problem is with the drive or the tapes.