When we get this message it is typically on the first job to write to the tape. A quick erase on that tape resolves the issue 75% of the time. For the other times we just chalk it up to a bad tape. I tried to erase a tape 5 times (once after each time that message came up) and it just kept happening.
On our side it may be due to a tape drive in our library failing, but it happens so rarely we haven't looked into it further. I hope you get some further information as it would be nice to see any other ideas for this.