While not strictly a valid ldif, the following works for me:
$> ldapadd dn: uid=testüser,ou=users,dc=example,dc=org objectclass: posixAccount objectclass: inetOrgPerson cn: test uid: testüser uidNumber: 37500 gidNumber: 37500 homedirectory: / sn: test
adding new entry "uid=testüser,ou=users,dc=example,dc=org"
so no preconversion of umlauts to base64 necessary. The searchoutput on the otherhand has the base64 conversion included:
$> ldapsearch -QLLL uid=testüser dn:: dWlkPXRlc3TDvHNlcixvdT11c2VycyxkYz1leGFtcGxlLGRjPW9yZw== objectClass: posixAccount objectClass: inetOrgPerson cn: test uid:: dGVzdMO8c2Vy uidNumber: 37500 gidNumber: 37500 homeDirectory: / sn: test
I noticed a missing space in the op dn though
dn:uid=Röichard,ou=newUsers,dc=cricbox,dc=in
^
hth