You have Apple devices in your environment and you are using IWA authentication (also applies to several other authentication methods). You notice that Apple users always fail authentication.
The problem lies in the design of Apple's software. While Windows machines are happy to provide the logged-on user's credentials to a proxy, Apple devices simply do not provide this data, even when explicitly queried. This will cause authentication to fail and users can not access the internet.
There are several possible workarounds, but they all aim for the same: No authentication attempts if the request comes from an Apple device (or authenticate them as a Guest user).
In OS X 10.6 Apple have started to support IWA. Mobile devices do not currently support IWA.
This is issue is typically the result of OS / Workstation (Apple) behavior. Factors to consider are as follows: