Hello there,
Are you using dynamic NAT? Backup Exec version 9.x does not support dynamic NAT.
http://support.veritas.com/docs/258334
The firewall must have a static Network Address Translation (NAT) configuration for the two-way communications to work between remote server and backup server.
Hope this helps you.
Thank You.