Teoricamente, deve funcionar assim: Os usuários devem poder fazer o login com suas senhas MD5, e sempre que mudarem eles receberão uma senha SHA512.
Difícil julgar por que as pessoas não podem fazer login com sua senha MD5. Autenticação com as senhas SHA512 funciona? Se você mudar temporariamente para o MD5 e alterar a senha de um usuário de teste, poderá fazer login nele? Talvez você possa postar as linhas de não-comentários /etc/pam.d/common-auth para dar uma olhada. E, claro, arquivos de log poderiam ter alguma informação de fundo.
Para o seu desejo de exigir que as pessoas alterem sua senha, você pode definir a data da última alteração como 0 em / etc / shadow. Por exemplo. para o usuário foobar
sudo chage -d 0 foobar