Hello,
-- As your exchnage server crashed and you ahve rebuilted the server, have you added the different hardaware, different netbios name/Ip address?
-- Remote agent is present on the remote server?
-- Verify if service account has admin role at all levels ie. site server.
-- enable restrict anonymous support on bothe the servers.
-- you can refer the following technoet:
http://support.veritas.com/docs/261150
NOTE : If we do not receive your reply within two business days, this post would be marked assumed answered and would be moved to answered questions pool.