FULL means it's full of valid data/backups that you will need to restore from.
You cannot change tapes with valid data on them to Scratch - that will automatically happen once all the backup images on the tapes have expired. If you are in doubt, run 'Images on Media' report to see which client backups are on the tapes.
You can also run 'Media List Report' (Tape List in 6.5) to see amount of images and Kbytes written.
Please explain how you did the following: "
I attempted to change out the label on one of them"...
If you physically pull off label A00000 and replace it with label XXXXXX, it still has an internal label of A00000. The moment tape XXXXXX gets mounted, the internal label of A00000 is recognized - NetBackup knows that this tape is full off valid, unexpired images. It will say something like the following in the logs:
'Expected XXXXXX, found A00000. FREEZING media....'
It will not allow the tape to be overwritten until all images have expired.
If you have a problem with your vault configuration and deferred ejects, you should concentrate your efforts on troubleshooting that...