Check your IIS logs to see if that reveals anything.
Of particular interest in the logs might be the HTTP status code, however the URLs they are browsing could be interesting in case there is some issue where your users are being incorrectly bounced between servers and the authentication isn't being passed through correctly, or even at all.
I haven't really looked much at the Exchange 2010 IIS logs, but if your users are being directed to a page similar to
you-put-your-password-in-wrong-you-numpty.aspx then that would probably be your definitive answer. In all seriousness though, if you purposefully authenticate incorrectly and see what that looks like in the IIS logs, you might see a similar pattern for other users (I'm thinking being directed to the logon page with some specific parameters in the query string like