Turns out that in additional to the message "Please insert overwritable media"... there was another message that was not showing up in the windows event log, but only in backupexec.
That message indicated "the media in drive xxxx is written in an unrecognized format. Erase the medium to make it usable."
This is a new server, so we only had about 10 tapes (also new) that had backup jobs on them. History showed all these jobs as successful. But we checked each of the tapes and they all produced the message above.
We ended up relabling all of them (thus losing all backups to this point-which in one sense did not matter because successful or not, BackUpExec wanted nothing to do with them) then moving them to the active media set. They then worked fine.
So in one sense I am glad the problem seems to be resolved. However, I am more than a little bit concerned as to what would cause all the tapes that we have used to date to become unusable. A backup is only good if you can use it, and a mass invalidation like this is scary.
If I did something really dumb I would really prefer to know that.
Any ideas on what may have caused this would be appreciated.