Disclaimer: I know nothing about HTTP::Proxy
Claimer: I know way too much about Basic Authentication (1)

I'm assuming url credentials like http://username:password@some.host/ aren't relevant.

LWP's GET -eSUd is a good debugging aid here. It'll show you the basic headers to compare to your own.

Another idea: put up your own server and watch the requests (or proxy your proxy to see what it's trying to do)

---
(1) I tried to write a module that would fallback to using the basic credentials as a pseudo-cookie if a client had cookies switched off. Many 401's and 30x's later I discovered that it wasn't practically possible if you want to support Mozilla and changing user(IE works though). "wasn't practically possible" is a big call, let's say I couldn't do it.