Your suggestion works perfectly! Thank you!

...

I'm assuming that auth_by_bind means that koha tries to bind with the openldap server using the username and password the user provided.

This is correct assumption.

...

I'm unsure where to configure HOW koha should bind with the ldap server... (something like uid=%s,ou=users,dc=blah,dc=blah)

<principal_name>uid=%s,ou=users,dc=blah,dc=blah</principal_name> should be enough.