Galera, após receber alguns telefonemas de amigos me perguntando se eu saberia como resolvê-la, cheguei a conclusão que mais pessoas estariam com o mesmo problema, pois então lá vai a resposta.

O Samba, para se autenticar no AD, utiliza o kerberos e este camarada precisa estar sincronizado em relação ao tempo com o servidor. Para resolver isto é simples:

Execute o comando:

ntpdate <ip ou nome do servidor AD>

para sincronizar o tempo, depois tente se autenticar novamente.

Valeu galera, espero que isto os ajude.

Abraços.