Você não diz qual tipo de cliente você usa, mas uma vez eu experimentei o mesmo comportamento, e isso se relacionou com as novas configurações padrão do cliente NTLM no Windows 7.
Versões mais antigas do Windows usam o NTLMv1. Como o NTLMv1 pode ser quebrado em minutos, a Microsoft mudou para o NTLMv2 no Vista. Infelizmente, o AuthenNTLM é bastante antigo e não é mantido e não retransmitirá corretamente as novas mensagens do NTLM para o controlador de domínio ativo. A parte um pouco surpreendente foi que, na verdade, não importava qual navegador eu usava: todos (IExplorer, Firefox, Chrome) aparentemente usavam os recursos do sistema operacional para lidar com as mensagens NTLM ...
A solução para mim foi escrever do zero PyAuthenNTLM2 (outro módulo para o Apache), porque o servidor não fazia parte do domínio e o AuthenNTLM era a única opção (o modntlm simplesmente não compilava). O PyAuthenNTLM2 manipula o NTLMv1 e o NTLMv2, mas é baseado no mod-python, não no Perl.
Vários sites na web sugerem ajustar uma configuração de segurança (bastante bem escondida) no SO do cliente para que o NTLMv1 antigo seja usado, mas eu evitaria isso. O NTLMv1 é simplesmente totalmente inseguro para os padrões atuais.