Backup Exec Port Madness
If 9000 doesn't work, try 10000. If 10000 doesn't work, try 9000.
Last night, all of my backups failed with the same communications error for all of the remote agents. Various error messages led me to numerous kb articles, forum posts, etc, but it turned out that my ndmp port setting of 9000 in the media server's \system32\drivers\etc\services file (set many months ago to fix a connection problem) stopped working, so I had to set it back to the default of 10000. Restarted the BE services and I could see the agents again.
No idea what would have changed, since there were no updates to BE, SQL or Windows in the past week except for the new MS KB2840149.