We have run into this problem a lot too.

I like to run "Format" on new tapes using the Native Windows Backup Utility as noted in the reply above.  The SQL Server Backup "format" handle does not seem to do the trick.

Good luck

This seems to work for us.