Hi Ryan,
Please follow these steps:
Stop all Backup Exec Services.
Rename the "Catalogs" folder to .old
Uncheck "Use Storage media based Catalogs" in Tools>Options>Catalogs.
Start all Backup Exec Services and then retry cataloging the tape and then try restoring.
============