Please refer to the following technote which mentions various reasons which may cause the job to fail.
Title:- How to determine why a Backup Exec for Windows NT and Windows 2000 job failed http://seer.support.veritas.com/docs/191165.htm
And,
Title:- How to find out why a VERITAS Backup Exec (tm) 9.x http://seer.support.veritas.com/docs/267107.htm
To isolate such issue, try splitting the backup job( for example C:, D: for local and remote backup ) and observe which backup selection is causing this issue.