As you noticed, only some users suffer this problem. So we need to first focus on client side. The choice of NTLM or Kerberos depends on the client side as the browser makes the choice.
If you really want to troubleshoot such a complex problem, the easiest way is to open a case via http://support.microsoft.com