This last week I was deploying Lync 2010 with Excahnge 2007 UM and I ran into the following error on the Exchange 2007 UM server.
The Unified Messaging server failed to exchange the required certificates with an IP gateway to enable Transport Layer Security (TLS) for an incoming call. Check that this is a configured TLS peer and that the correct certificates are being used. More information: A TLS failure occurred. The error code was "-2146893052" and the message was "The Local Security Authority cannot be contacted"..
After doing some research, I found out the problem was related to the Exchange 2007 UM role being deployed on Server 2008 R2.
Fortunately, Exchange 2007 SP3 adds support for Server 2008 R2 and once it was installed everything worked as expected.
Here is the Technet article that covers Exchange 2007 SP3.