Hello,
Make sure that the version of the remote agent on the Media Server and the remote server are same.
Check the version of beremote.exe on both the servers.
Push install the remote agent if the versions are not matching. Every time we perform a live update on the Media Server, we need to update the remote agents by pushing out. Its not an automated process.
Symantec KB:
http://support.veritas.com/docs/238993
How to check the version or status of the Remote Agent for Windows Servers (RAWS) on remote servers from the Backup Exec Graphical User Interface (GUI)