UPDATE <4/06/2005> Thanks Randy!
The customer having this issue followed up and identified the root cause to be an invalid Certificate Revocation Path on the certificates.
Users connecting to LCS 2003 configured for TLS with Windows Messenger 5.0 could connect successfully. After upgrading to Windows Messenger 5.1 they would fail the connection with the error:
A TLS connection could not be made. Please wait for your network administrator to correct this problem, and try again later.
The cause of this problem is with the Certificate Revocation List (CRL) and how each client handles it. Windows Messenger 5.0 will not treat a failure to get the CRL as fatal but the Windows Messenger 5.1 client will. If you capture the client logon with Network Monitor or Ethereal then you can see the LDAP or HTTP connection attempt.