OK by no means am I an expert but: I just tested mine with my N900 on sidekick plan (just switched). Going to web prompts for a username/password then connects, Nokia Messaging account in email appears to refresh without problems, and my "availability" flashes then show green connected. I only have the proxy setup for http and https, I've left the others blank. EDIT: Availability went green before launching the browser, so not going through the proxy.

I would try adding the first couple lines auth_param and
When I first set it up following the link I posted, I used:
acl myusernameUser proxy_auth myusernameUser
http_access allow myusernameUser

which didn't work until I switched it to
acl myusername proxy_auth myusername
http_access allow myusername

My latest setup works as posted using ncsa_users, which should only allow a user in the passwd file. Wish I could help more, just going forward blindly on my own as well.