Na minha experiência, ao usar o Basic Auth apenas os primeiros oito caracteres da senha são importantes. Ou seja cripta trunca a senha antes de fazer sua mágica.
Acho que as limitações do Digest Auth são diferentes, mas eu teria que procurá-las para contar a você.
Isso não ajuda muito no seu problema. Esses usuários problemáticos podem fazer o login se os nomes de usuário / senhas forem digitados por você mesmo ou simplificados para palavras do dicionário? Pode estar relacionado a uma diferença de mapa de teclado.