host all all <blah> ldap "ldap://server:389/ou=People,dc=example,dc=com;uid=;,ou=People,dc=example,dc=com"
It's very important to have the:
...;uid=;,ou=People,dc=example,dc=com
Postgres is not automatically pre-pending the attribute name and it's not appending the basedn. Also note... the comma before the basedn. If you don't have that their, it won't work.
After that, login to the database as superuser and type:
create user <usernamefromldap>
You can't login to pg via ldap unless you have created the user in the db first.
If that doesn't work, check your ldap server logs. Also, is this really openLDAP or AD? I've seen wackiness with AD even though openLdap was working with the same basic schema.