These users lack necessary fields for being able to log in.
This attributes are a standard part of objectClass: posixAccount.
Also, you should look to your /etc/nsswitch.conf as is it may not have ldap as a source.
The server certificate in your chain is a self-signed one, with a CN containig 'example.de', which looks like an example (as long as you aren't managing ldap.Example.de).
s:C = DE, ST = Example, L = Example, O = Example, CN = ldap.Example.de
Just remove it and use a proper issued one (and don't forget to attach the complete certificate chain).
This setting only applies when you're using the RFC 3062 extended operation, i.e. using ldappasswd. Just editing entries with normal LDIF operations won't work. If you want to seed entries with an encrypted value, use slappasswd to generate the hash.
Edit: Looking specifically at the ldapvi documentation, it appears to use an LDIF-like format with some ...