check for your auth type:

 cntlm -M http://www.google.de

adjust config file /etc/cntlm.conf:

 Username        USER
 Domain          DOMAIN
 Workstation     WORKSTATION
 Header          User-Agent: Mozilla/5.0 (Windows NT 6.3; rv:36.0) Gecko/20100101 Firefox/36.0
 NoProxy         localhost, 127.0.0.*, 10.*, 192.168.*
 Proxy           1.1.1.1:80
 Proxy           1.1.1.2:80
 Listen          3128
 #Auth           LM
 Auth            NTLMv2
 #Auth           NT
 #Gateway        yes

create obfuscated passwords for conf file:

 root@ganglia:/etc/nagios3# cntlm -H
 Password:
 PassLM          E17DDA60707E0D9A552C4BCA4AEBFB11
 PassNT          F6A4E906DE5825A15ED696A913C56F94
 PassNTLMv2      68C8370655425F24D93D0AA9F54850EA    # Only for user 'USER', domain 'DOMAIN'

and add them to cntlm.conf

Test in Foreground:

 root@ganglia:/etc/nagios3# cntlm -v
 section: global, Username = 'USER'
 section: global, Domain = 'DOMAIN'
 section: global, PassLM = 'E17DDA60707E0D9A552C4BCA4AEBFB11'
 section: global, PassNT = 'F6A4E906DE5825A15ED696A913C56F94'
 section: global, PassNTLMv2 = '8C8370655425F24D93D0AA9F54850EA'
 section: global, Workstation = 'WORKSTATION'
 section: global, Proxy = '1.1.1.1:80'
 section: global, Proxy = '1.1.1.2:80'
 section: global, NoProxy = 'localhost, 127.0.0.*, 10.*, 192.168.*'
 section: global, Listen = '3128'
 section: global, Header = 'User-Agent: Mozilla/5.0 (Windows NT 6.3; rv:36.0) Gecko/20100101 Firefox/36.0'
 Default config file opened successfully
 cntlm: Proxy listening on 127.0.0.1:3128
 Adding no-proxy for: 'localhost'
 Adding no-proxy for: '127.0.0.*'
 Adding no-proxy for: '10.*'
 Adding no-proxy for: '192.168.*'
 cntlm: Using following NTLM hashes: NTLMv2(1) NT(0) LM(0)
 cntlm[14262]: Cntlm ready, staying in the foreground