Could be your catalogs have got themselves confused.
Try:
1.) Stop all Backup Exec (BE) services under Tools/Backup Exec Services
2.) Go to the installation folder for BE and rename the "catalogs" folder
3.) Restart all BE services
4.) Verify that new "catalogs" folder was created
5.) Insert tape
6.) Goto "Device" Tab, Inventory and catalog tape
7.) You should now see the catalog under the "Restore" tab
8.) Restore your data