Hi,
This scenario is explained here:
http://www.cisco.com/en/US/docs/voice_ip_comm/connection/7x/user_mac/guide/7xcucmac110.html#wp1049902
If Cisco Unified CMBE is integrated with an LDAP directory, you must start by deleting the LDAP user that corresponds with the Connection user. When Cisco Unified CM data is next synchronized with the LDAP directory, the user is deleted from the Cisco Unified CM database. When the user no longer appears in Cisco Unified CM Administration, you can use Connection Administration to delete the user from the Connection database.
Note If LDAP synchronization is not enabled and if you do not manually synchronize Cisco Unified CM data with the LDAP directory, the deletion of an LDAP user is never replicated to the Cisco Unified CM database, and the corresponding Connection user cannot be deleted.
Hope that helps,
Brad