I am running into the same problem. My nightly backups finishing with a Job Status of 'Recovered' and the error: e00081d9 - The Backup Exec job engine system service is not responding.
However, the jobs seems to start up again 5 minutes after the previous job ends.
I too have called support with a 'critical' issue and am waiting for a response.
If anyone has a fix for this I would love to hear it.