Open a SSH session with root and fire up this command;

tail -f /var/log/auth.log

Open a new SSH session and try to login with the other user. What is the error shown in the first screen (the one with the tail command)