Thank you sooooooooooo much! I’ve been investigating for so long, and combination of all the above helped me with similar problem (on my Ubuntu 18.04.3, Samba 4.7.6 as AD DC, Nextcloud 17. 0.1 with PHP 7.2.24 on apache2). Especially Dr. Kiljan’s article helped, and it is the best Samba AD howto I’ve seen, so it’s a pitty I haven’t encountered it earlier - and thanks a lot for giving that link!
So first, I confirm that for me it appears to be some bug in nextcloud - that for a password change operation, nextcloud searches the user by UUID, but using configured attributes (name/email). This wrong ldap search filter being used I saw in /var/log/samba/log.samba (which I configured by putting “log level = 5 auth:5” into smb.conf). And the message on nextcloud password change webpage was “Wrong password”.
So adding objectGUID to the “login attributes” helped here - now the user was at least found in AD. But beware that you might need some other attribute than objectGUID - e.g. if you’re using some other LDAP than Samba AD. You can e.g. try ‘uid’ or one of [‘entryuuid’, ‘nsuniqueid’, ‘objectguid’, ‘guid’, ‘ipauniqueid’] that are mentioned in nextcloud/apps/user_ldap/lib/Access.php
But the problem changed to another, with a message “Unable to change password” (what’s interesting, Nextcloud sent an email notification anyway, stating to the user that their password has just been changed - but still the old password was set).
So, secondly, the LDAP user dedicated to nextcloud integration could not reset password, but the “domain administrator” seemed to be able. So for the dedicated nextcloud user, I added permission to reset passwords (but via RSAT), and still it did not work. I am not sure if I tried to add this user to Administrators and/or Domain Admins groups. But when I changed the dSHeuristics setting using ldbedit (apt install ldb-tools) - just as Dr. Kiljan wrote - then password changing by a nextcloud user finally worked! 
What’s iteresting, it even works over unencrypted connection (ldap server require strong auth = no # this setting perhaps needs whole machine reboot), so I guess TLS is not a problem here.