Eu não acho que você pode usar a mesma porta para HTTP e HTTPS. Tente alterar o HTTPS para uma porta diferente no Firefox e no arquivo de configuração do cntlm.
Eu instalei e configurei o cntlm em uma nova compilação do Ubuntu 12.04 de 64 bits (rodando no VirtualBox).
A configuração do Network Proxy está apontando para cntlm ( localhost:3128 ) para os proxies HTTP e HTTPS.
Por meio do Firefox, as URLs http funcionam, mas os URLs de https ficam perpetuamente bloqueados ao tentar se conectar.
Qual é o problema?
Eu não acho que você pode usar a mesma porta para HTTP e HTTPS. Tente alterar o HTTPS para uma porta diferente no Firefox e no arquivo de configuração do cntlm.