Após algumas horas sem dormir, finalmente encontrei o erro: O tempo do sistema nas duas máquinas estava desligado a mais de 5 minutos do horário do servidor. Isso fez com que o sistema de autenticação do kerberos falhasse.
Ainda não tenho certeza, por que essas máquinas não recebem a atualização automática de hora (afinal, o servidor samba 4 deve estar atuando como servidor NTP), mas o principal problema está resolvido.