Users can login to web applications successfully (so issue is not "web login" issue).
However, users cannot login to Sametime via the Sametime Connect or the embedded Notes Client Sametime awareness.
In addition, login attempt returns "server unreachable" or "home server unreachable".
Check the Sametime field for the user in the Domino Directory. Make sure the correct FULL hierarchical name of the server is in this field. The common name by itself no longer works.
The long answer is evidently, the Sametime server doesn't recognize Person doc having just the Sametime server's common name. So it goes off looking for another non-existing Sametime server to hand off the user (the login id). Obviously, it will never find it. The result is that to log in successfully, the Person document Sametime server must be empty (blank) or have the full hierarchical name.