Download and install cntlm package from : http://sourceforge.net/projects/cntlm/
Edit /etc/cntlm.conf
Give credentials in the below fields
username
domain
password
proxy IP:Port
Note down the Listen port… say it is 3128
save
Select Network options in Ubuntu and choose network proxy
Give 127.0.0.1 port 3128
/etc/init.d/cntlm restart
Thats it !
theG 