Hello,
There are a few things to check, most notably..
1. The Backup Exec Remote Agent build version is the same as the backup server. (If not, completely uninstall, reboot, reinstall, and reboot again.)
2. The Exchange server has been rebooted since the Remote Agent has been installed, and...
3. How's your transfer speed between the two? Try copying a 50MB file and see how quickly it transfers. If it takes more than a minute on 100mbps, start looking at duplex/speed mismatches, replacing cable, and new NICs and/or drivers.
---cheers
shirmal