This could happen if the PORT 10000 is in use by another application.
On the remote server running Remote Agent for Windows Servers:
1. Open Services from the Control Panel for Windows NT 4.0, or go to Start | Programs | Administrative Tools for Windows 2000 and Windows 2003
2. Stop the Backup Exec Remote Agent for Windows Servers service
3. Go to Start | Run, and type CMD to display the command prompt window
4. Type netstat -a and press . This will list all the ports that the server is listening on.
5. If there are any entries for port 10000, then this port is in use by another application. Chage the port number of that application to another number.
Incase changing the port number for another application is not an option then you will have to change the port number for remote agent.
http://support.veritas.com/docs/255498
Make sure the following:
1) Remote agent service is up and running on the remote server under services applet, it should always be running under services applet.
2) Make sure remote agent build is same as backupexec build.