After a few sleepless hours, I finally found the error: The system time on the two machines was off more than 5 minutes from the server's time. This caused the kerberos authentication system to fail.
I'm still not sure, why these machines do not get the automatic time update (the samba 4 server should be acting as NTP server after all), but the primary issue is solved.