Sounds to me like authentication is succeeding. The only thing that I know of that could prevent the user from appearing as authenticated after the authentication has happened is if cookies are blocked somehow. There is configuration that can prevent passing cookies if the request is not using https as mentioned in the article Use SSL but it is not configured this way by default. Other things that can block cookies are things like any kind of privacy guard security software (or bowser toolbars), do not track mode in web browsers etc.
I would try different browsers and different client machines to see if you get the same result.
The only other thing I can think of to try is adding this in user.config:
<add key="UseTransferRequestForUrlReWriting" value="false"/>
which would change back to the old way we were doing url rewriting. I don't really see how that could affect authentication but its one of the few recent changes that could have side effects in some environments.