Wacky backup problem...

I'm using NTBackup on NT4 Server (SP6) with a Conner CTT8000-A (uses TR-4 cartridges), and I'm getting an error any time I try to catalog following a full backup. The error is:

"Tape device reported an error on a request to space backward by file marks"

Since it blows up any time it tries to catalog, this means I can't perform incremental backups, and I won't be able to restore (which kinda defeats the purpose of backing up).

I am backing up a particular local directory set aside specifically for backups (it's a little over 2 GB in size). If I backup a subset of this directory--any subset--I can catalog just fine. However any time I perform a full backup on the whole thing... boom.

I've already tried using different tapes, I've tried running scandisk on the drive containing the backup directory, I've tried slightly different backup settings. I have yet to try running a tape cleaner through the tape drive (it's on order), but I have used canned air on the interior of the drive and it does look pretty clean.

Right now I've removed all PCI cards except for the video card and network card, reseated the IDE cables to the CTT8000-A and am trying a full backup again (after which I'll test catalog again).

Anyone have any ideas? I'm running out of things to test/check. Has anyone encountered this before?