Ahh, if you're having difficulty using a windoze proxy server, I feel your pain. I've been through this, and found a solution.
Grab the following python script from:
http://toastytech.com/evil/msproxy.html
and run it on your Redhat box. This will get you past the authentication issue you're having.
On a side note - this very same question was one of the first I asked on this forum, along with my own answer to it. Did you try searching before asking the question?