A single machine somehow managed to have a differently-configured /etc/krb5.conf file and recently stopped all (both ssh and on the console, except for root) logins from working. The messages in the logs were of the form:

Sep 29 15:04:58 test-host sshd[1433]: pam_unix(sshd:auth): authentication failure; logname= uid=0 euid=0 tty=ssh ruser= host=host.example.com user=user12345
Sep 29 15:04:58 test-host sshd[1433]: pam_krb5[1433]: authentication fails for 'user12345' (user12345@REALM.EXAMPLE.COM): Authentication failure (KDC has no support for encryption type)
Sep 29 15:05:00 test-host sshd[1433]: Failed password for user12345 from 1.2.3.4 port 50432 ssh2

The reason for this was simple – the Kerberos config in /etc/krb5.conf contained the following lines:

[libdefaults]
        ... (other lines snipped)
        default_tkt_enctypes = des-cbc-crc
        default_tgs_enctypes = des-cbc-crc

These settings force the use of an older DES encryption type which is only 56-bit, and has been disabled since Windows 7/Windows Server 2008 R2. Removing these lines so that the encryption type is automatically negotiated allows stronger encryption to be used which is supported by the Active Directory servers, allowing us to login once more. Phew!

(This is a legacy CentOS 5 server, all the newer ones have the same Kerberos config on them — thankfully the same config works on CentOS 5/6/7 and Debian/Ubuntu without modifications thus far!)