Code:
PasswordAuthentication yes
# Change to no to disable s/key passwords
#ChallengeResponseAuthentication yes
ChallengeResponseAuthentication no
...
#UsePAM no
I think you want "UsePAM yes" if your system has PAM installed.
Get regular use authentication working before disabling root logins. The fallback backup/restore option posted earlier may be a good idea as well. Also, log in twice. Keep the first terminal connection open. That way, after making changes; logging out and trying to log in again, you can use the first connection to reverse changes you made that locked you out.
Try logging in with "ssh -vv user@host". It may provide more details at the client what is going on.
You might want to post your appropriate PAM configurations. Start with "ssh" and check what others are included in the "ssh" file. Concentrate on SESSION entries. Also double check if some PAM messages are posted in /var/log/messages.
Which Linux or BSD distro does the server run? You might try downloading the package for openssh, and extracting the PAM config files that are installed by the openssh package. Are there any differences?
If this is a Fedora, or RHEL Server. Your mention of SELinux implies that it is. You can determine which package supplies a file with "rpm -qf /path/to/file"; verify a package with "rpm -qV packagename".
You can also download the openssh rpm package, and extract files inside with "mc" (a filemanager) or using "rpm2cpio" and then "cpio" or using "unrpm". The first option "mc" can be used on a non-rpm based system. Check the PAM config files that the package supplies. Also check the PAM files that are used to authenticate users.
Concentrate on differences. The installers may have added specialty PAM library, and then added an entry for it. Comparing the packages' PAM config files against what you have could pinpoint where a problem might be.
The
http://rpm.pbone.net site is a good place to locate & download RPM packages for a particular distro. Use the Advanced option and select the particular Red Hat or Fedora distro you are using.