I am using the Lync 2013 client for a while now and noticed that the Presence does not update based on Calendar infomation.

Starting the Lync 2010 client gets the correct Calendar Presence right away without any problems.
That means that Exchange Autodiscover and Webservices are working as expected.

There is a problem with Updating the Lync Presence based on Calendar information in certain conditions with Lync 2013.
It may be related to email address configuration but still researching how this can be fixed.

Other people are also reporting this issue in the Lync forums at Microsoft Technet.

UPDATE 13/2/2013
I can confirm that Lync 2013 Februari Update (CU1) fixes the issue
http://www.pro-lync.be/blogs/lync2013/archive/2013/02/12/update-for-microsoft-lync-2013.aspx