Just a bit more info... the LDAP user is also present in /etc/samba/smb.conf in the valid users = directive.
I changed the samba log level in OMV and now I'm getting some more useful messages in the system logs.
Code
smbd[782573]: check_ntlm_password: Authentication for user [my-ldap-user] -> [my-ldap-user] FAILED with error NT_STATUS_NO_SUCH_USER, authoritative=1
I've just read somewhere that samba uses sambaNTPassword attribute from the user's LDAP info to check for the samba password... So now I'm trying to add that and see if it works... (and if that works next step will be to somehow instruct samba to use the "normal" password or somehow keep that in sync with sambaNTPassword, so there's no need for 2 passwords...)