Are you able to ping the Backup Exec server from the remote computer and vice versa. You also may want to confirm a trust has been established by right clicking on the remote server from the Backup Exec console servers list, and selecting the option for "Establish trust".
Also confirm the following possiblities:
- Firewall is blocking the communication.
- Antivirus is blocking the Backup Exec services
- IPv6 is enabled on one server
- The publishing tab of the remote agent has an incorrect entry for the Backup Exec Server name or IP address