Hello Tim,
Thankyou for pasting the error. Please ensure you have installed the following patches.
VERITAS Backup Exec (tm) 9.1 for Windows Servers revision 4691 - Service Pack 3
http://support.veritas.com/docs/278302
9.1 4691 Hotfix 54 - Backup Exec for Windows Servers - Remote Agent Authentication Vulnerability *Requires Backup Exec 9.1 4691 Service Pack 3
http://support.veritas.com/docs/278467
Please make sure that you are using a logon account which is a system logon account.
How to create a System Logon Account in Backup Exec 9.x and 10.x for Windows Servers
http://support.veritas.com/docs/274012
Let us know if this helps. Check if the SP1 firewall has been activated, please deactivate it and try backups.
NOTE : If we do not receive your reply within two business days, this post would be marked ‘assumed answered’ and would be moved to ‘answered questions’ pool.