I just had a case where the users experienced that presence in the Lync client did not update based on the calendar information unless they restarted the client completely. Relogging did not help.
The weird thing was that on the users contact card they would be listed as busy, but their presence was still available.
After quite a bit of troubleshooting and some help from colleagues, I ended up removing CU2 (the April 2011 update, gives version .275 to the client). This removed the problem completely. So, if you are having presence issues with Lync, try removing CU2 for now.
This might be a bug?