Hello,
Such problems could also be due to the unneccessary Catalog files or also catalog corruption. Please try performing the following :
Stop all the BE services, rename the Catalogs folder (under C:\Program Files\Veritas\Backup Exec\NT) to Catalogsold. And now start all the BE services.
If incase the catalogs are of great concern then delete the unused or the catalogs that are no longer needed.
Please write back to us if the issue persists & also if there are any error messages in the Event logs or in Backup Exec.
NOTE : If we do not receive your reply within two business days, this post would be marked "assumed answered" and would be moved to "answered questions"pool.