Here’s a bizarre simple little fix! I’ve had a server which kept getting stuck on “Queued” when manually running a cleaning job. To get the jobs running again I had to either reboot the server or restart the Backup Exec services.
To get around this, go into devices, right click on the server and select “Paused”. Do the same and unselect “Paused” and the cleaning job should spring to life!