Das Problem ist gelöst!
Schuld war libxcrypt mit der Version >= 4.4.21 (Achtung ich benutze ArchLinux). Folgende Newsmeldung ist dort enthalten:
https://www.archlinux.de/news/34044-libxcrypt-und-schwache-Passwortverschluesselungen
Ich habe das ganze mittels "downgrade libxcrypt" auf die Version 4.4.20 gesetzt und schon funktioniert wieder alles. Vielleicht ist es für andere hilfreich. Danke für Deine Hilfe d00p!
EDIT: Habe in Froxlor in den Sicherheitseinstellungen nun Sha512 ausgewählt und alle Passwörter neu erstellt. Nun funktioniert alles auch mit der neusten, angebotenen Version von libxcrypt.