I don't know details of your Windows network environment, but have you tried passing the user id in the form of "ntdomain\username"? That's worked for me when I've been behind a Microsoft proxy. Very simple example at "(code) LWP with auth proxy".
cheers,
Don
striving toward Perl Adept (it's pronounced "why-bick")
Update: Ignore me and listen to brother meetraz. 8^p