>При добавлении новой записи, вида $dn = "cn=Иванов Иван Иванович,dc=example,dc=ru" получаю ошибку

Надо попробовать каким-нибудь LDAP-клиентом, если сработает, то
проблема в перловских библиотеках. Сталкивался с подобной ситуацией, вылечилось
правкой файла схемы OpenLDAP'а. Какого не помню: давно дело было. Смысл в том, что
описание cn выражается через формат без поддержки юникода. Меняем описание и всё работает.