First, have you checked your server's settings?
Here's a link on a PDF describing which ports need to be opened:
Then you'll need to set up a series of tests to pinpoint where exactly the problem occurs. Unfortunately, I can't give any detailed advice. Each server configuration is different. And you'll also need to check if any of the necessary ports are blocked by your ISP (which is usually the case with educational institutions & libraries).
Hello, found your post. I realize it's been 6 months since you posted, but I have a solution for you since I have struggled with the same problem since 2009.
I discovered that when the iPhone is using LDAPS, it tries to bind with LDAPv2. After it binds, it speaks LDAPv3 like it is supposed to. Apparently this is a somewhat common practice since OpenLDAP includes an option for it.
You'll want to set the following option in OpenLDAP:
Walla! LDAPS works! (assuming you've correctly done all the certificate stuff). Took some deep reading through the debug logs to figure out this problem. Figured I'd share my answer with others.