Do you have enough licenses for the remote clients/servers? Does the account the BackupExec Server services are running under have the appropriate rights to this server?
As for the different IP's/nics, only one of them should have a default gateway. If one is an external IP (or NAT'ed to an external IP) and one is a private IP, is the Backup Server on the same network segment as the private IP (i.e., no router needed to get from Backup Server to remote agent...no firewall between)?
If the remote server has the Windows Firewall running, can you temporarily turn it off (and disable the external IP if there is one) to see if it is an issue? There should be an exception for BEREMOTE and for port 10000.
Also, the remote agent can seem to install fine when in fact it has had an issue. You have to look at the bkupinst.log file (in the Windows directory, or WINNT, ...). The latest entries will be at the bottom. If there was an error it will be in there.