Possible Cause:
1. Firewall blocking the access to these ports between Policy server and LDAP server.
2. LDAP server down
3. If using ssl (not in your case as you are using 389 port which is non ssl ) , certificate invalid/Secure connection option not checked.
Questions :
1. Can you share the screenshot of the User Directory configuration from Admin UI?
2. Are you able to perform view contents for that directory ?
3. Are you able to install some external LDAP browser tool like JXplorer and perform similar bind/search to the same directory and see if that works?