I was receiving this error on only one person's machine. If I used their account on other machines, I would get the same error on the Lync client. It was denoted by a red X in the bottom right of the client. The problem ended up being some sort of corruption in their Exchange email box. I backed up their current mailbox, disabled their current mailbox and then created a brand new mailbox. The error went away after doing this. I was able to recreate the issue by disabling the new mailbox and then reconnecting them to their old box. It was a bit annoying for the user while you're moving mail around but oh well! Dont forget to grab their Exchange Server side rules as well before you blow away the old box, or before the system blows it away for you. I'm not sure how the email box got corrupted, but this was my fix!
I am running Lync Server 2010 and Exchange 2007.
***UPDATE***July 15, 2011***
Based on one of the comments to this post, I did some additional research. The person who posted about the bad character with the contact is yet ANOTHER fix to this issue.
I deleted all the users contacts (they were left in the deleted items). Then I closed Outlook and Lync, then reopened Outlook and then Lync..... the error went away!
I moved the contacts back in blocks of 10-15 at a time trying to isolate the contact and repeating the process of opening and closing the apps. I finally got the error to come back on one of the iterations. I ended up isolating the issue to a single contact and I noticed that there was a strange character at the end of this contacts phone number. It looked like a square or in binary terms, a null byte. As soon as I deleted this "square" I was able to move this contact back and the error did not come back. Then, I moved all the rest of the contacts back in and fortunately, there were no other contacts that had this issue.
I suspect that an easy solution to this for a person who has a lot of contacts would be to export them all to a CSV file then delete the user's contacts. I don't think the special characters would make it to your export so all you would have to do is import them as new contacts. Maybe someone can test this and let the readers know.
Thanks again to the "anonymous" poster for the additional information to spark this investigation!