In the person document in the directory, do they have a home sametime server specified, if they do, is it a server that exists? Compare it to a user that can login. Try removing it to see if the user can login. This is what I would imagine is happening.
What version is the Sametime Client and what version is the Sametime Server.
Do you have the full Sametime Server installed, or the Sametime entitlement server installed, if rich clients cannot login, but notes clients can, it sounds like you may have that.
Your Sametime server maybe restricting which client versions can login (this is controlled in the Sametime.ini) you can test that theory using a tool like this:
Another thing - the user can log in correctly from HTTP on Sametime Server (http://serwer.acme.com/names.nsf?login).
This is a bit of a red herring, as the authentication for the web component (Domino) is different to the authentication for the Sametime Client.