Kindly refer to the following technote link which might be helpful to you.
Title:- How to protect Exchange 2000 and 2003 servers using the Backup Exec for Windows Servers Exchange Agent
http://seer.support.veritas.com/docs/266074.htm
Also, we would like to mention you that if your exchange server is remote to Backup Exec server, then kindly re-install remote agent on Exchange server again.
Please revert back with exact error message that you come across in order to troubleshoot the issue further.
