This issue should Have been fixed with HotFix 320467 for Backup Exec for Windows Servers version 12.5
Because of the large increase in GRT items that are restorable with 12.5, an increase in time should be expected and is by design.
To supplement faster GRT backup times using the 12.5 SharePoint Agent, a disk backup could be considered as it will not require and "Updating Catalogs" stage during backup.
When backing up a SharePoint Portal Server (SPS) content database to tape with the setting 'Enable the restore of individual documents from the database backup' enabled, the job will go to an 'Updating Catalogs' status before completing. Depending on the size of the content database, the backup job may remain in this status for an hour or more. This status is displayed as the SPS database contents are enumerated to provide the granular restore selections for the tape backup.
Workarounds:
1. Perform backup to disk instead of backup to tape media. During backup to disk operations, the cataloging portion of the tape backup is not performed as the granular restore selections are created from the disk image instead.