A. Your problem seems to be specific to Backup Exec 8.5 and Backup Exec 8.0, and the culprit is a corrupted catalog file. Fortunately, this problem is fairly easy to repair.
Go to your Backup Exec application directory, and find the catalog directory. Rename this directory catalogold (or something similar) to show that this directory isn't the current catalog directory. The next time you run Backup Exec, the application will recreate the catalog directory and start a new catalog file.
You might want to scan through old catalog files to try and determine when the catalog problems began. If you can find the instance, then you should be able to copy all catalog files dated before the apparent corruption to your new catalog directory. After you do so, prior backed-up catalog files will be visible in Backup Exec, and restoration from earlier backups will be easier.