I get the same erro on a Windows 2003 Standard Install.
I have updated Veritas to lastest SP, reinstalled the Remote Agent several times, chnaged the logon account for the BE services and even created a new job to attempt to resolve.
I get the Following:
Error: a000846b, The job failed with the following error:
Device could not be backed up because an error occurred while connecting to the Remote Agent for Windows Servers.
Make sure that the Remote Agent for Windows Servers is running on the target computer.
Please remember this is a strictly local backup.