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