Проблема таки решена!!!
- cntlm !!!
Для связки Ubuntu 10.04 - SQUID с NTLM-авторизацией помогает cntlm.
Кому актуально, так и запишите.
1. Ставим cntlm.
2. В /etc/cntlm.conf прописываем:
Username логин
Domain домен
Password пароль
Proxy ххх.ххх.ххх.ххх:хххх
Listen 5865 (или другой)
3. Прописываем проксю 127.0.0.1:5865 для apt-get в глобальных настройках прокси, для синаптика - в его собственных и радуемся.
Не знаю что там с ntlmaps не так (у меня ставилась версия 0.9.9.0.1-10ubuntu1).
Пытался ковырять конфиг ntlmaps. Это либо не давало эффекта, либо приводило к неработоспособности.
Вобчем, cntlm рулит.