I'm having trouble keeping my servers connected to our openLDAP server.

All through syslog I see messages like this:

Sep 26 14:06:01 hostname nslcd[930]: [2aeb87] connected to LDAP server ldaps://ldap.domain.com/
Sep 26 14:07:01 hostname nslcd[930]: [aae0a3] ldap_result() failed: Can't contact LDAP server
Sep 26 14:07:01 hostname nslcd[930]: [74310e] ldap_result() failed: Can't contact LDAP server
Sep 26 14:07:01 hostname nslcd[930]: [aae0a3] ldap_abandon() failed to abandon search: Other (e.g., implementation specific) error
Sep 26 14:07:01 hostname nslcd[930]: [b2a65f] ldap_result() failed: Can't contact LDAP server
Sep 26 14:07:01 hostname nslcd[930]: [b2a65f] ldap_abandon() failed to abandon search: Other (e.g., implementation specific) error
Sep 26 14:07:01 hostname nslcd[930]: [74310e] ldap_abandon() failed to abandon search: Other (e.g., implementation specific) error
Sep 26 14:07:01 hostname nslcd[930]: [73c9b8] ldap_result() failed: Can't contact LDAP server
Sep 26 14:07:01 hostname nslcd[930]: [73c9b8] ldap_abandon() failed to abandon search: Other (e.g., implementation specific) error
Sep 26 14:07:01 hostname nslcd[930]: [73c9b8] connected to LDAP server ldaps://ldap.domain.com/


I'm at the point where I want to start blaming the server, but this is happening on all the new servers I am bringing up (Ubuntu 10.04) and not on the older servers (8.04).
Everything seems fine and we can sudo and su with our ldap accounts and then out of no where "so-and-so is not in the sudoers file".  A simple "id user" re-establishes the connection and all is well again for a while. 

Has anyone else ran into this and finally, permanently made it work?