I just found a resolution to this error. The media was allocated by EMM. Here is how to release the media from EMM.
Run the following command. Redirect it to a text file.
(cd \NetBackup\bin\admincmd)
nbrbutil -dump
Within this "dump" output, look for the following section:
MDS allocations in EMM:
MdsAllocation allocationKey=29 jobType=1 mediaKey=4000001 mediaId=AZZ001 driveKey=2000001
driveName=Single_DDS drivePath={3,0,6,0} stuName=Magg masterServerName=1time
mediaServerName=1time ndmpTapeServerName=
Within this section, find the media id. In this case, AZZ001 is the media id that is in use. Note the allocationKey for the media id in question.
Then, run the following command, noting the MDS allocation key of the media. In this case, it would be "29"
nbrbutil -releaseMDS
In my NBU environment I had several media allocated by EMM and no activity in Netbackup. After releasing all the media from EMM the expired media changed to "available media"