Quick followup: if the OP's transcript of 'ldapmodifyuser' is indeed complete than it's pretty obvious why the search fails - the user entry simply doesn't have a 'host' attribute.
I see. The problem is the missing host attribute. After adding 'host' the problem is fixed.
I used ldapadduser to add the users. The figuration did not have a host fields before.
Now, I've added one line in the figuration. Is this the correct way to avoid this problem in the future? Thanks.
$ grep host /etc/ldapscripts/ldapadduser.template host: *