Same thing happened to me.
When you specify a dedicated backup network on the media server, and then 'push' the remote agents to servers, info about that dedicated network is incorporated into the remote agent install on the servers.
Seems that SP 1 has a bug and the remote agents no longer know about the dedicated backup network.
Try this:
On one of the remote servers, navigate to the 'pgm files\veritas\backup exec\RANT' folder. Run the 'vxmon.exe' pgm.
This puts an icon in the system tray. Right-click and choose 'Options'.
On the 'advertising' tab, enable advertising, enter the (backup network) IP address of your media server. Add it, and apply. Also stop & re-start the 'backup exec remote agent' service.
If it works, you need to do this on each remote agent server.
Cheers