Somewhat by accident I fell on a squid configuration that will seamlessly proxy Windows XP workstations and Windows 7 workstations (both RC and gold) using NTLM negotiation.

Previously I had tried different combinations of auth_param negotiate and auth_param ntlm. The NTLM negotiation would work for Windows XP, but not Windows 7 (unless you edited the registry in Win7, which I did not want to do in production.) Negotiation wouldn't work for anyone.

Then I failed to complete an edit and hit the magic combo that works. I think this is technically a broken configuration as far as Squid goes, but it gets the job done.

1) update samba to 3.3.6 from backports. We're still using winbind, so the samba setup is the same as for proxying Windows XP with NTLM.
2) Set your auth_param lines in squid to look like this:

auth_param ntlm program /usr/bin/ntlm_auth --helper-protocol=squid-2.5-ntlmssp
auth_param negotiate children 15
auth_param negotiate keep_alive on

It looks funny with the ntlm program line and negotiate children and keep alive lines, but it does work. Both Windows XP and unmodified Windows 7 happily authenticate with IE or Firefox.

After spending lots of time playing with stuff like kerberos authentication and not having much success, this little broken config made for a happy day.