Are you able to ping by name and access shares on the other machines. eg \\servername\c$
Have you tried this:
http://seer.support.veritas.com/docs/278397.htmIt involves selecting a specific NIC for Backup Exec to use and then ticking the box saying it can use any available NIC or protocol if the remote agent is not on the selected subnet. I have checked and confirmed this is still an option on Backup Exec 12.5d