Thanks Craig,

Yes they all have full copies: One is the master and the other two have R/W copies.
The container I have set is at the Org level. The setting looks like "/MC_BOE/MCBOE" with MC_BOE is the tree and MCBOE is the Org.
The communication status is green and the connections of the three servers all have checkmarks by them.

I had only the master in there until this issue reared it's head and looking at other TIDs/posts I was thinking maybe an LDAP communication issue. So I added the other two to help, but it didn't. It was about that time I noticed the users that were working had the connection limit unchecked and the non-working users had it checked. I upped the connection limit to 2 and that actually fixed most of them, but not all. Per Mr. Rosen's post, I plan to go back and remove the check from all users but haven't had time yet.

I guess comparatively, our eDir is small. A rough guess is about 2500 - 3000 objects.