NetBackup 7.5.0.6 - Status 58 - Windows Server 2012

Are these seperate networks? The FROM 0.0.0.0 and <ip address> ? Is there a hardware firewall or any special routing between the NBU server and the target server?

From NBU server are you able to do a reverse lookup of the target? You can check it both ways with something like:

On NBU server:
bpclntcmd -hn <client name>
bpclntcmd -ip <client IP>

On Client:
bpclntcmd -hn <NBU servername> 
bpclntcmd -ip <NBU IP>

You can try running this from the NBU server too:

bptestbpcd -client <target_hostname> -debug -verbose

Is master server also the only media server? If separate media server, have you tested connectivity and lookup from media server as well?

Have you created bpcd log folder on the client? 

We need to see if connection attempt has reached the client.

Status 58 is normally caused by one of 2 things:

reverse lookup issue on client side (bpcd will confirm)

firewall problem (no bpcd log created is a sign, telnet to port 1556 and/or 1724 will confirm)

The fact that this is a newly installed client could also mean that server host_cache id not yet updated. We normally need to refresh host cache when new client is added or updates to DNS and/or hosts files are made.

NBU automatically refreshes host_cache once every hour, so, if this was the issue, connection should work by now.
To manually refresh host_cache:
bpclntcmd clear_host_cache