The best method to troubleshooting this issue is to look at the more detailed connection attempt results in a debug of the Job Engine on the media server. To generate a debug:
To put the Backup Exec Job Engine into Debug Mode please do the following:
1. Stop the "Backup Exec Job Engine" Service. this can be done by going to the Start Menu and going to the Settings | Control Panel | Administrative Tools Menu and selecting Services
2. double click on the "Backup Exec Job Engine" Service, and from the "General" tab locate the "Start up Parameters" input field
3. in the input field type the following "-debug" (do not include the quotation marks)
4. Select the start button to start the service in debug mode.
5. A -bengine debug log will be created in the Backup Exec\Logs directory
Also, for the telnet session to the Remote Agent itself (this may sound silly), but did you see a smiley face & a heart? If so, then your connection to the RA was good.