Access Denied - Credentials Missing when browsing SharePoint 2010

A proxy authentication error is usually a 407 response? Are you getting a 407? And if so, do you have an HTTP profile applied that's configured to do explicit forward proxy?

You're browser will send an authorization header (with NTLM token) if a) the server sends a 401 Unauthorized response with the "WWW-Authenticate: Negotiate" (or "WWW-Authenticate: NTLM") header, and b) the browser is configured to be able to send credentials to the website. in IE you do this by adding the URL to the Trusted Intranet Sites list.