I am having the same problems and it started a few days ago. But it's happening on a server that is being backed up, not the media server. So the only Backup Exec item installed is the remote agent. Here is my error when I try to start the service:
Could not start the Backup Exec Remote Agent for Windows Systems service on local computer. Error 1067: The process terminated unexpectedly.
The service is running under the system account and always has. But I changed it to my account, a domain admin, the service started. So then I started a job and it began and then failed due to an authentication error. I opened up the job and checked the user credentials against the server and it failed (access is denied) for me and the system account on this one server, but not other servers in the job.
Like I said, it just started a few days ago. I've rebooted the server, uninstalled, reinstalled the agent etc., but not luck.
Any help would be greatly appreciated.
Thanks.