В принципе, я эту проблему решил.
Причина была в использовании в rumakeindex двух странных символов,
которые в koi8-r идут перед буквами. Это сделано для ранжирования по
алфавиту, но в итоге sed в локали utf-8 спотыкается на них.

Я переписав rumakeindex, благо, там совсем немного, заменив tr двумя
последовательными вызовами sed. Теперь всегда выдаётся нормальный
*.ind, если локаль utf-8.

Правленую версию прилагаю, прошу проверить.

Может, если с ней всё нормально, протолкнём в апстрим?

> Вешать на texlive-bin, воспроизводится даже при вызове rumakeindex без параметров,
> но только в локали ru_RU.UTF8.