This could be a result of not having enough NTLM/LDAP authenticators allocated by your system to handle all the authentication requests you are receiving.

A possible solution is to increase the amount of authenticators from the 'System Setup > Authentication' tab. 10 is the default amount but for users in the hundreds at least 30 is recommmended.

To complement an increased amount of authenticators you may also consider enabling IP Sessions from this same tab. With this enabled once users have authenticated themselves via their username and password, their IP address will be recorded and used for authentication for the remainder of the session, which cuts down on the amount of authenticators required by the system.

It should be noted that in an environment which uses terminal servers you will have to list all your terminal server IP addresses is System Setup->Authentication.