That fixex it for me too. Thats a bit of a bug somewhere! I could run backups in BE 12.5 but all utility jobs would get stuck queued...
Under Devices section and Right clicked on media server name where attached devices are listed and clicked "Paused" once and then a second time to get queued jobs to go through.
