I came across an interesting problem recently where some Windows XP and Windows 7 clients running Communicator 2007 R2 couldn't sign in over a Lync 2010 Edge server. We had migrated our environment from a 2007 R2 Edge to a Lync Edge server and all Lync 2010 clients were fine.
After making a few calls and doing some research I found this article: http://blog.tiensivu.com/aaron/archives/1917-OCS-2007,-NTLM,-and-Edge-server-login-problems.html
As it turns out we had to disable the requirement for 128-bit encryption on the Edge and Front-End Lync 2010 servers for it to be resolved. No reboot was required. See the above link for instructions on how to do so.