On the SQL server, open the Backup Exec Agent Utility. Under security, make sure the name/ip address for the media server is correct and that from here, you can ping the media server using the exact name listed there. You can also add the Backup Exec media's IP address as well.
From the Media Server right-click the SQL server and select establish trust after making changes on the Utility Agent on the remote server.
