After TS for hrs, we discovered that basically the LDAP (optional) configuration fails for no good reason, since we finally gave up with UPM and configured CUCM for LDAP, and it worked like a champ.
This sounds like something that should be submitted to Cisco TAC. Have you communicated with them? If so, do you have a case number?
Were you ever able to make any headway with this? I have a similar situation. I opened a case with TAC. They escalated it but it has been quite a while with no answer.