Проблема с Samba

Попробуй удалить этих пользователей из домена , а потом добавить заного, у меня помоголо, удачи

До такого простого решения я бы и сам додумался. Однако не помогает

Внимательно посмотри чем юзера отличаются - которых пускает и которых нет. Может быть у них пароль русскими буквами и не перекодируется правильно в нужную кодировку, а может в клиентских системах особенность какая-нибудь.