It's possible it's your load balancer setup.
Does this happen if you shutdown one of the Connection Servers? If this is not easy for you to test, perhaps instead you could test this by connecting to a specific Connection Server instead of using the load balanced alias. This will help to narrow down the cause.
Also, you should look in the Connection Sever logs to see why the Connection Server authentication to AD is failing.
Sorry for the delay in response. I'm not seeing much in the connection server logs that pinpoints this particular issue. It's definately not a connection server problem since both respond to all requests. Any ideas what to possibly look for in the log? I don't see anything that stands out.