The Utility jobs (Inventory, Unlock, Erase Tape, etc) show as "queued" and never run or end in a "Recovered Status", but the backup and restore job runs without any problem.
The above mentioned problem occurs if the Backup Exec database has the Server Status flag set to indicate that the server is "Paused" but the Backup Exec console is unable to display that status in the Backup Exec User Interface.
3. Go to the Devices tab of Backup Exec, right click on server name, "Pause" & then "Unpause" the server.
4. Restart all Backup Exec services from Tools-->Backup Exec services.
5. Again go to BeUtililty and check the server status. It should now show as "Running".
6. Run the utility job again.
1. Upgrade to Backup Exec 2010 R3 SP2 which can be found here
2. Perform the first solution again after upgrading.