with the information you have provided it appears your backup servers' ability to store catalogs is intact (its not a database or catalog storage problem). Your attempt to catalog the tape provided no data, and your overwrite protection is set to none leads me to think the tape has been overwritten. If a tape is used more than once with your settings, the previous data will be removed from the catalog and restoration will be impossible via backupexec.
The job logs do not reflect the catalogs- the job logs are just logs recorded at the moment of the backup and they are not linked to the catalog or the media database in any way.
If you have the support tools loaded on your server (or download from microsoft) the tool called mtfcheck.exe. Using this tool, you could check the header information of your tape and see what is available on the tape.