Users unable to send over SMTP after upgrade to Exchange 2013

Solution 1:

I finally called Microsoft to get this resolved. The issue appeared to be permissions on the "Client Proxy" HubTransport receive connector. They went into ADSI Edit, Configuration -> Services -> Microsoft Exchange -> DOMAINNAME -> Administrative Groups -> Exchange Administrative Group -> Servers -> SERVERNAME -> Protocols -> SMTP Receive Connectors, then went to the properties for the "Client Proxy SERVERNAME" entry.

Then, on the security tab, went to "Authenticated Users" and made sure "Accept any Sender" and "Accept Authoritative Domain Sender".

Once these were set it began working. I'm not sure what the defaults would be, and if these are the defaults, why ours was not set to that. We didn't change anything with the built in receive connectors.