Backup Exec and HP Ultrium 215

I have an issue with my backups. First the backups suddenly quit working so I upgraded the firmware for the HP SureStore Ultrium 215. After doing that the backup seems to startup but then gets an error stating the drive needs to be cleaned. I cleaned the drive multiple times and used brand new cartridges but I am still receiving that message. I backup using Veritas Backup Exec version 8.5 on a Netware 5.1 machine.

Any help is much appreciated!

Chris