Проверить, в какую учетную запись они логинятся и меняют пароли - локальную или доменную,
чутье подсказывает, что в локальную.
У 3-4 пользователей почему-то не подходят пароли
то есть они их ставят, работают, комп блочится и зайти уже невозможно,
Я бы не верил в чудеса, и не доверял бы пользователям создание пароля самостоятельно. 95%, что они его забывают (т.е. задают Oleg12345 а пишут oleg12345).. Сможете проверить человеческий фактор?