I am having a similar problem.
Both links in this thread supplied by Veritas Support do not result in technotes of any kind.
I have recreated the job and checked the selections at the request of Veritas Support (not sure why this would make any difference) but still the job is failing. I have uninstalled all traces of Veritas software from the server in question and removed it completely from the Backup Exec application, then fully installed it again checking the correct permissions are assigned to the directories I want backing up - job fails again.
Seems like Veritas do not know what is causing this.