Solution 1:

You must use the RFC 3062 Password Modify Extended Operation. See the README in the source distribution (there is no man page, AFAICT). You can do this from the command line with OpenLDAP's ldappasswd (which is different to slappasswd which just hashes password values in various ways).

userPassword has grown special semantics over time, none of which were intended (and which are not strictly compliant with the specifications). It's not uncommon for it to have "compare only" (authenticate only) access or no read access, and have client or server dependent transformation (e.g. client-side or server-side hashing of content). Password Modify is well defined and accepts only plaintext passwords, and can use an administrator defined hash method. This extension provides an abstraction layer for passwords (and also allows for password storage to be decoupled from the directory entirely). It's also needed for password complexity enforcement, that can't be done if clients are allowed to write pre-hashed valued directly to userPassword.

e.g. (perl): http://search.cpan.org/~gbarr/perl-ldap/lib/Net/LDAP/Extension/SetPassword.pm

You can confirm support by querying the Root DSE (dn ""), e.g.

$ ldapsearch -H ldaps://myldap/ [ -D user -w password ] \
 -s base -b "" "(objectclass=*)" supportedExtension 
[...]
dn:
supportedExtension: 1.3.6.1.4.1.1466.20037    # STARTTLS
supportedExtension: 1.3.6.1.4.1.4203.1.11.1   # password modify
supportedExtension: 1.3.6.1.4.1.4203.1.11.3   # who am i
supportedExtension: 1.3.6.1.1.8               # cancel request

Solution 2:

Since the existing answers seems a) lacking in detail or b) advocating a pointless schema addition that is no longer required, I've written up a post that explains how to enable smbk5pwd in simple terms here.

What's actually lacking from the original question description config is the module configuration, not the krb5-kdc schema. The Kerberos schema is not required for syncing Samba passwords.

Short version:

Create smbk5pwd-overlay.ldif

dn: olcOverlay={0}smbk5pwd,olcDatabase={1}mdb,cn=config
changetype: add
objectClass: olcOverlayConfig
objectClass: olcSmbK5PwdConfig
olcOverlay: {0}smbk5pwd
olcSmbK5PwdEnable: samba
olcSmbK5PwdMustChange: 0

And apply with

sudo ldapmodify -Q -Y EXTERNAL -H ldapi:/// -f smbk5pwd-overlay.ldif

olcSmbK5PwdMustChange is the password expiry time in seconds, like 5184000 for two months, or 31968000 for annual changes with a five day grace period. 0 means no expiry.