I assume you used the following TSM command:
YOURTSM> audit library 4560LB checklabel=yes
Here's the text of this error from the TSM 5.4 Messages manual (sorry I don't have the one for TSM 5.5).
ANR8912E Unable to verify the label of volume from slot-element (element-address) in drive (drive name) in library (library name).
Explanation: The volume from the slot that is identified by the element address is loaded into a drive. The drive cannot be opened following the load. The label cannot be read to process the volume.
System action: The volume is stored, and processing continues with the next available slot.
User response: Check the system error logs for errors reported by the drive that are related to this volume. Make sure that the cartridge is not a cleaner cartridge that would have been loaded by mistake. If the cartridge is a cleaner, issue the QUERY LIBVOL command to get the correct storage slot for the cleaner and move the cleaner to that slot. If the cleaner is not in the library’s inventory, use the CHECKIN LIBVOL to check the cleaner in. During Audit Library, remove the bad volume from the reported slot and run Audit Library again.
End of Message
The label that cannot be read is the magnetic label on the tape, not the barcode label. The fact that the robot can pick the tape and put it into the tape drive and put it back into the slot again, suggests this is a drive issue and not a robot/picker issue. However this involves multiple drives, which is weird, so the system error log might be helpful here. If the barcode reader couldn't read the tape barcode, I think you would get a different error as well. It's odd that the Library is fixated on these slots, and since you've changed the magazine already, it can't be the slots. Multiple slots and multiple drives being involved at the same time, suggests something different.
We have an older IBM 3583 tape Library, and it does weird things on occasion. USUALLY this Library has to be rebooted or power cycled to clear a strange error that doesn't otherwise make sense. OCCASIONALLY, IBM service has found some bad hardware (including the robot/picker) to fix a weird error. RARELY IBM service had to do an alignment/calibration of the robot/picker to correct a weird error. The cleaner cartridge solution is novel and could apply, but we've never had a cleaner in a regular tape slot before.
Hope this helps.