I'm in a test environment using VMware with the simplest of scenarios as possible...
I have 3 servers, all 2008 R2 SP1 and 2 XP desktops for OWA access
LyncAD - domain controller and CA
LyncExch - Exchange 2010 SP1 rollup 5
LyncSrv - Lync 2010
Working in a domain of Lync.Company.com
The certificate installed easily thru the wizard in LyncSrv and I used the Exchange Management Console commands for requesting and importing the certificate for Exchange. I also used the Certificate Console to import the intermediate certificate in the Intermediate Certificates folder as well as the Trusted Root Certificates folder.
Everything appears to be configured correctly with no apparent errors.
When accessing IM thru OWA on one XP, the green light shows up for the user currently logged in, but shows a white light for the other XP user. When I right click on the other user, the option for chat is available. When I click on it, the IM dialog comes up and allows text to be entered. Shortly after it is entered the message pops up, "This message couldn't be delivered to all recipients because some recipients are offline or don't want to be disturbed."
Then shortly after that, the orange box displays at the top of the IM dialog with "This conversation is no longer active and its contents haven't been saved. Please copy them if you need to keep them."
Looking at the Lync Server Control Panel, under the Topology settings, the Exchange server status shows N/A while the Lync server shows the online icon.
Reading previous troubleshooting steps, I did generate a new certificate, but I get the same result.
I followed the directions from http://blog.schertz.name/2010/11/lync-and-exchange-im-integration/
I enabled SIP Stack logging in Lync and get the following...