Wrong Search Base
If a search request is missing the -b option for specifying the search base, then, by default, Penrose is searching the LDAP server's root DSE instead of Penrose's virtual LDAP tree.
ldapsearch -h localhost -p 10389 "cn=John Doe" cn
Searching the root DSE requires you to specify "-s base" for base scope, otherwise it's rejected by the underlying LDAP library.
The correct search request should be:
ldapsearch -h localhost -p 10389 -b "dc=Example,dc=com" "(cn=John Doe)" cn