One thing you could try is retiring the media and deleting it from inside of Backup Exec. To do this go to the media tab, find the media you are trying to catalog. Right click on them, select associate with media set, then select retired media and click yes to all. Once they are all in Retired Media, select all of them again and delete them (right click and select delete). Once that has been completed inventory the B2D folder again, and attempt the catalog again.
Also, just out of wondering but what is the Overwrite Protection set to for the media set the backup to disk files belong to?