Для початку набери LANG=ru_UA.koi8-u і знову подивись на локаль якщо і це нічого не дасть тоді зайди в папку /usr/share/locale/ru_UA (чи щось в цьому дусі коротше зайди туди де в тебе знаходиться локаль) і в цій папці ти побачиш файли з такими ж іменами про які тобі написало (LC_NAME, LC_MESSAGES, і так далі) відкрий кожен файл і в ньому напис koi8-r заміни на koi8-u якщо побачиш там якісь ще каталоги то таку процедуру пророби і з файлами і в цих каталогах. По ідеї якщо ти все зробиш правильно і поперемінюєш все так як і потрібно то все має запрацювати.
p.s. Це кустарний спосіб напевне це все можна зробити і елегантніше але я думаю краще все зробити руцями чим довіряти якійсь команді чи графічному конфігуратору якщо і це не поможе то таке зроби і в супутніх каталогах що знаходяться в каталозі locale (міняєш koi8-r на koi8-u і тільки)!