Nach ein paar schlaflosen Stunden fand ich schließlich den Fehler: Die Systemzeit der beiden Maschinen war um mehr als 5 Minuten von der Serverzeit abgelaufen. Dies führte dazu, dass das Kerberos-Authentifizierungssystem fehlschlug.
Ich bin immer noch nicht sicher, warum diese Maschinen nicht die automatische Zeitaktualisierung erhalten (der Samba-4-Server sollte eigentlich immer als NTP-Server fungieren), aber das Hauptproblem ist gelöst.