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.

Additional Information

This is issue is typically the result of OS / Workstation (Apple) behavior.  Factors to consider are as follows:

• The proxy will send the same authentication requests to the client machines regardless of OS installed and it's up to the client machine to respond accordingly 
• IWA is a Windows fundamental method of authentication (Integrated Windows Authentication). Apple devices (MACs) only began "supporting" IWA as of a certain OS X release (OS X 10.6 - even then many issues were reported in the Apple forums regarding IWA)
• Windows machines obtain NTLM tokens upon login, whilst MACs do not.
• Many customers, with the aid of the Apple support team, have worked around this issue by implementing Kerberos authentication. 
  Note: Implementing Kerberos does not guarantee a resolution to the problem you are experiencing.
• Apple devices are outside of our realm of support, (primarily because said devices run a proprietary OS).