Could be there are other network components that are still not forwarding the message.
In one environment there was a WebCache plus Apache HTTP Server (OHS). First WebCache was not allowing a header greater than a configured value.
[SOMETIME] [webcache] [ERROR:32] [WXE-12400] [http] [ecid: 3259741227814,0:1] HTTP request-header exceeds configured maximum individual header size ( Authorization: Negotiate YIIjVQ... (10200 bytes) ). Client IP: SOMEIP [SOMETIME] [webcache] [ERROR:32] [WXE-11355] [frontend] [ecid: 3259741227814,0:1] Single request header length exceeds configured maximum. A forbidden error response is returned to the client. Client IP: SOMEIP [SOMETIME] [webcache] [ERROR:32] [WXE-11381] [frontend] [ecid: 3259741227814,0:1] A request is sent for a forbidden operation.
The value 'Maximum individual header size' of WebCache was set to 16000, after that the HTTP Server started to complain.
[SOMETIME] [OHS] [ERROR:32] [OHS-9999] [core.c] [host_id: SOMEHOSTNAME] [host_addr: SOMEIP] [pid: 9526] [tid: 1282525504] [user: oracle] [VirtualHost: main] request failed: error reading the headers
This was resolved by setting 'LimitRequestFieldSize' to 16000 as well.
Note that WebLogic has a default of 1000000 - http://docs.oracle.com/middleware/1212/wls/WLMBR/mbeans/ServerMBean.html?skipReload=true#MaxMessageSize).
In the end we increased the values of both the WebCache and OHS to 32000 (as this is the maximum Kerberos ticketsize a client can present).
So it could be in your case that some users are still presenting a too large a header size such that the network components are rejecting the request (note that this is done in order to prevent denial of service requests, so it could also be beneficial to rethink your LDAP structure instead of increasing all the protocol acceptance limits). I think WebLogic with 1000000 bytes is OK, but just to be sure check the settings (these can be found in the protocols tab of a specific server, the general tab contains the general settings that can be overridden by a protocol specific one).