Not trying to Hijack this thread, but for me the server I am having an issue with is the Media server so I am not using an agent.
My current work around is that I am using NTBackup to backup the system state to a file and then using Backup Exec to ...
I am running in to the exact same issue, but using Backup Exec 12 on a WIndows 2003 server which is a DC. I too have tried all the above links and nothing seems to fix it. KB@INF were you able to get this resolved at all?