I have a HP 960 Ultrium 3 tape drive. Since I got it, (second hand, £90) I've been experiencing shoe-shining. Writing with tar in Linux, I average about 3Mb/s write speed. I've tried replacing both the SCSI card and the cable now, both of which made no difference at all. A curiuos observation I have made is that the write rate is not consistent. Sometimes it will write for over a minute without shoeshining, but more often, just a few seconds. I've also tried several tapes, different source drives, and even writing from Windows Backup, to no avail.
SnapOverflow
Shoe-shining refers to the tape drive stopping and rewinding due to an empty data buffer or inconsistent incoming data stream. This was a problem with older DLT drives. LTO drives shouldn't experience shoeshining. The LTO format/standard was partially designed to eliminate this behavior. HP drives, in particular, have a variable write speed to help reduce this effect. The Ultrium 960 should shift down to 27Mb/s as a minimum streaming speed.
We're missing some of the information that could be helpful in diagnosing the issue...
Tell us about your actual hardware setup. Looking at a local HP Ultrium 960 drive, I'm getting write speeds of ~2,000 Megabytes/minute (33Mb/s) across a mixed data set (with hardware compression ON). This is with an HP ProLiant DL380 G6 server and an HP-branded LSI Ultra 320 SCSI HBA.
As you have access to a Windows system, download HP Library and Tape Tools. L&TT can run a wide variety of tests and report things which may be set up incorrectly.
One thing to try is using a cleaning tape and see if this helps. Otherwise, I am guessing that the write head is broken, creating many write errors that get detected by the verify-after-write functionality.
3Mb/s is slow so there probably is a hardware problem as the other answers suggest. However, even when this is fixed, from a single server (depending on hardware and what you are running) you might have trouble writing to the tape fast enough to prevent shoeshining.