WORKSFORME

root@wrars-comp /home/wrar # locale
LANG=POSIX
LC_CTYPE="POSIX"
LC_NUMERIC="POSIX"
LC_TIME="POSIX"
LC_COLLATE="POSIX"
LC_MONETARY="POSIX"
LC_MESSAGES="POSIX"
LC_PAPER="POSIX"
LC_NAME="POSIX"
LC_ADDRESS="POSIX"
LC_TELEPHONE="POSIX"
LC_MEASUREMENT="POSIX"
LC_IDENTIFICATION="POSIX"
LC_ALL=

Проверялось на Compact RC2 и на текущем сизифе.
Последовательность действий:
1. Запуск KDE.
2. Меню -> Terminals -> Terminal (Super User Mode).
3.
# locale
LANG=ru_RU.KOI8-R
LC_CTYPE=ru_RU.KOI8-R
LC_NUMERIC=ru_RU.KOI8-R
LC_TIME=ru_RU.KOI8-R
LC_COLLATE=ru_RU.KOI8-R
LC_MONETARY=ru_RU.KOI8-R
LC_MESSAGES=en_US
LC_PAPER="ru_RU.KOI8-R"
LC_NAME="ru_RU.KOI8-R"
LC_ADDRESS="ru_RU.KOI8-R"
LC_TELEPHONE="ru_RU.KOI8-R"
LC_MEASUREMENT="ru_RU.KOI8-R"
LC_IDENTIFICATION="ru_RU.KOI8-R"
LC_ALL=
(Это в офисе. Дома вместо KOI8-R везде UTF.)

wrar@wrars-comp ~ $ rpq xterm
xterm-196-alt1
wrar@wrars-comp ~ $ rpq kdelibs
kdelibs-3.4.0-alt4
wrar@wrars-comp ~ $ rpq kdebase-common
kdebase-common-3.4.0-alt3

исправлено забыл когда, в kdebase-3.4.1-alt8 точно 

fixed