Ensure that your server name matches the one in exchange. To find this name in exchange 2013 navigate to ECP > Servers and select your server and click edit, Then click Outlook Anywhere and use the internal host name.
Mine ended up being mailservername.domain.local