Hi O_Looman
It sounds like you may have a port issue with NDMP. See if the TechNotes listed below help.
The first TechNote (link below) describes your error but only cites Backup Exec 10d. The ports are the same in version 11d so this resolution will apply. Most of the TechNotes refer to RedHat Linux so you will have to take the information and apply it to your particular OS.
How to change the NDMP communication port of the Remote Agent for NetWare with Backup Exec 10.x for Windows Servers
Unable to start the Backup Exec 10.x Remote Agent for Linux and UNIX Servers (RALUS) on a RedHat Linux system.
How to determine the Network Data Management Protocol (NDMP) port status on the remote Linux (Redhat) system in Backup Exec 10.x and 11.x for Windows Servers.
How to change the port for Network Data Management Protocol used by Backup Exec Remote Agent for Linux and UNIX servers on a UNIX/Linux machine
Finally I discovered this recent information
When creating a selection list for backup, attempts to browse a platform running the Remote Agent for Linux/UNIX Servers (RALUS) fails with an error An error was encountered while attempting to browse the contents of.... The media server could not connect to the remote computer. The remote computer may not be running the Backup Exec Remote Agent for Windows/Linux. Make sure that the correct version of the Remote Agent is installed...
Upon investigation, it is found that RALUS is not binding to the NDMP port on the IPv4 stack. It is doing so on the IPv6 stack. This may be confirmed using netstat -a. This occurs no matter what is defined for the NDMP port in /etc/services. The RALUS debug has the error, "Can't start listener: Error Code: 125, System Error Message: Address already in use".
It may be possible, however, to utilize the legacy agent for your particular platform to obtain backups. Please contact Technical Support for assistance with this option.
Here is the link to the Legacy UNIX agent but keep in mind that I have not had any success getting this agent to work with version 11d. It seems 11d only works with the RALUS agent.
VERITAS Backup Exec (tm) 10.0 for Windows Servers - Agent for UNIX version 5.046 (Legacy Agent)