I don't know what is wrong with this but here's what I would check for starters:
-Check your local mail queues on the Nagios server and see if they are backed up.
-Check the mail related files in /var/mail and /var/log/mail for any error messages indicating where the problem may lie
-Are there any devices in between that could be blocking the mail traffic?
-Is there a local firewall on the Exchage server blocking the access somehow?
-Telnet on port 25 to your Exchange Hub Transport server to check the connectivity through.
-As Lokiz mentioned, check that your Nagios server's hostname/IP is allowed to relay mail in your Exchange Organisation
Hmm can't think of anything more atm, give those a try for now I guess.