Usually when a Backup Exec remote agent refuses to respond and stopping and starting the service does no good (verifiable by creating a new job and attempting to connect to the remote server, only to find the drive selection boxes greyed out), the solution is to reboot.

There's a last-resort method more appropriate for production servers.

Telnet to the remote server on port 10000. As in:

telnet 192.168.1.2 10000

When I did it, I got a bunch of garbage characters. I closed the window, then tried to connect again. This time, the agent was awake.

I have no idea if Veritas sanctions this or not, but it worked for me, and I like the answer a lot better than rebooting.