You say that you have labeled all the tapes and put them in a media set. That would be where you problem is, as you shouldn't put the new tapes into the media set yourself, you should let Backup Exec to put them in there once it has done the backup job. Basically, once you put the tape into your media set, from that point, what ever overwrite protection period you have in place will then be applied to the tape.
If you look in the media section, look at the tapes and see if they are coloured black or blue, if they are black then you won't be able to overwrite the tape as the protection period is still in effect. If you move all the tapes into the Scratch media set, the overwrite protection period will be cleared, and you should then be able to run your job.
Keith