Hmph. That slapd.conf looks fine.
This could happen if you added some indexes to slapd.conf _after_ adding the entry you are searching for - then that entry would not be indexed, which would tell slapd that it does not match your search. If you did the rootdn search afterwards, that should have failed too, but maybe you misremember in which order you tried things. Anyway: Stop slapd, run sbin/slapindex, restart slapd, and see if that helps.
If not, you could try to move these statements below the 'database' section:
access to attrs=userPassword,userPKCS12 by self write by * auth access to attrs=shadowLastChange by self write by * read access to * by * read
and keep an access to * by * read above as well. Shouldn't matter, so if it helps you've found a bug...
That's all I can think of.