Selk,
Procurei aqui na internet para ver o que achava, e olha só:
http://www.flatmtn.com/article/setting-squid-ntlm-auth Nesta página, tem tudo explicadinho. Não é para o Ubuntu, mas Squid é um só, é só ignorar os procedimentos de compilação. Estou considerando é claro que o Squid nos repositórios está compilado com o winbind (para a autenticação NTLM).
Os pontos relevantes:
1) Configurar SAMBA (/etc/samba/smb.conf):
[global]
workgroup = [WORKGROUP]
netbios name = [MACHINE_NAME]
password server = [PDC]
security = domain
winbind uid = 10000-20000
winbind gid = 10000-20000
winbind use default domain = yes
Isso vai fazer o winbind pegar e mapear os usuários e grupos nessa faixa descrita acima.
2) Configurar o SQUID (/etc/squid/squid.conf):
# note: you may need to increase children based on your number of users
auth_param ntlm program /usr/lib/squid/wb_ntlmauth
auth_param ntlm children 5
auth_param ntlm max_challenge_reuses 0
auth_param ntlm max_challenge_lifetime 2 minutes
auth_param ntlm use_ntlm_negotiate off
auth_param basic program /usr/lib/squid/wb_auth
auth_param basic children 5
auth_param basic realm Squid proxy-caching web server
auth_param basic credentialsttl 2 hours
# only need this if you want to use Windows Domain Groups for acl(s)
external_acl_type nt_group ttl=0 concurrency=5 %LOGIN /usr/lib/squid/wbinfo_group.pl
Essa parte acima configura o helper que vai fazer a autenticação e algumas acls baseadas em grupos para serem utilizadas pelo squid.
3) Inserir o seu servidor no domínio PDC e iniciar os serviços:
iniciar samba
smbpasswd -j [DOMAIN] -r [PDC] -U [user_name]
iniciar winbind
4) Teste básico da rede Ruindows:
wbinfo -t (teste para ver se se juntou ao dominio, deve retornar "Secret is good")
wbinfo -a [domain]\\[user]%[password] (Teste para ver se está aceitando o NTLM)
5) Teste do helper do Squid:
./wbinfo_group.pl
[domain]\[user] [domain]\[group]
Deve retornar OK ou ERR. Para sair, CTRL+C
Isso é o básico, daí é testar pelo squid.
Resumi bastante, para ver se ajuda, não é muito complicado não, mas na época foi um saco mais por causa de permissões no PDC que eu não tinha, mas de resto funciona que é uma beleza, inclusive você pode logar com o squid o nome do usuário junto com a requisição, fazer acls para restrições por usuário e tudo mais.
Espero ter ajudado.
Abraços...