Currently on a Lync Server 2013 deployment where the client has Exchange 2007 deployed and are currently in the process of migrating to Exchange server 2013. All of the current Lync pilot users who have their mailbox on Exchange 2007 have no issues connecting with exchange since the Lync client will use a mapi connection to get the calendar information.
All of the Lync pilot users who are also Exchange 2013 pilot users started receiving this pop up in the Lync client.
When we were talking directly to Exchange 2013 there were no issues, the error started showing up when the Exchange team added Citrix Netscalers into the environment.
With a little troubleshooting and speaking with Citrix directly they explained that we needed to turn off persistence ie. Set Persistence to NONE for the exchange virtual servers because of the new way Exchange 2013 handles requests.
Here are some great articles that explain the requirement for no persistence.