j'ai rencontré ce type de problème mais ma configuration devait être très différente...
si ton dns ne traite pas les enregistrements srv, tu as un messages du type que tu as indiqué ...
dans mon cas, pour accroché une machine au domaine, j'utilise la forme netbios du domaine qui correspond dans ta conf samba au workgroup si tu as déclaré ton samba comme PDC.
je raccroche d'abord la machine au domaine en utilisant son nom netbios puis je redémarre la machine et je me loggue avec un utilisateur valide sur le domaine.
il peut aussi y avoir un problème avec la transmission crypté des mots de passe, il existe un petit script dans le cederom freeeos-station qui s'appelle clefregistrexp qui corrige se problème.
http://free-eos.org/