Os usuários fizeram logoff do domínio e fizeram logon novamente desde o momento em que você os adicionou ao grupo? O token de acesso / segurança de um usuário é gerado no logon e as alterações nesse token (alterações de associação ao grupo) só são afetadas quando um novo token é gerado no logon.