Hi,
I posted earlier that the solution suggested by "jimhollis" (to download cntlm) worked. However, after a while, and because of the complexity of the setup and of the proxy, the CNTLM solution stopped working 😐.
After looking around on the web for an alternative, I found the best (in my opinion) proxy handling software called "Proxifier".
After I installed it, and set it up (its basic setup is very easy, just create the proxy settings using the software instead of iTunes), and everything works perfectly. I then read the documentation, and extended my use of "Proxifier" to include almost all of my windows installed applications and software (IE, Firefox, Chrome, Office Outlook, Windows Update, MSN, Skype... everything.. and MOST IMPORTANTLY iTunes).
Although it is a bit expensive (30 something $) for me it was worth every penny.
http://www.proxifier.com is the website where you can purchase and download proxifier. (although there are other ways of getting it 😉)
I understand that some of you might say that this is not a good solution because of the network infrastructure and domain issues and all that, but even though that it needs an effort to install and configure on all domain machines, but it will help believe me. And of course, you can still have your proxy policies apply the same to everyone (same as it was before using proxifier), not to mention that it is a full installable application, that means you can set it up and secure it so that the users can not modify it at will.