Сабж:

В пакете docs-informatika, в t7/branch, description в кодировке ru_RU.koi8r
Предполагаю что и в p7 то же.

$ locale
LANG=ru_RU.UTF-8
LC_CTYPE="ru_RU.UTF-8"
LC_NUMERIC="ru_RU.UTF-8"
LC_TIME="ru_RU.UTF-8"
LC_COLLATE="ru_RU.UTF-8"
LC_MONETARY="ru_RU.UTF-8"
LC_MESSAGES="ru_RU.UTF-8"
LC_PAPER="ru_RU.UTF-8"
LC_NAME="ru_RU.UTF-8"
LC_ADDRESS="ru_RU.UTF-8"
LC_TELEPHONE="ru_RU.UTF-8"
LC_MEASUREMENT="ru_RU.UTF-8"
LC_IDENTIFICATION="ru_RU.UTF-8"
LC_ALL=


$ apt-cache search informatika
docs-informatika - п÷я─п╟п╨я┌п╦я┤п╣я│п╨п╟я▐ п╦п╫я└п╬я─п╪п╟я┌п╦п╨п╟.
docs-informatika1 - Практическая информатика, Часть 1
docs-informatika2 - Практическая информатика, Часть 2


$ LC_ALL=ru_RU.koi8r !!
LC_ALL=ru_RU.koi8r apt-cache search informatika
docs-informatika - Практическая информатика.
docs-informatika1 - ������������ �����������, ����� 1
docs-informatika2 - ������������ �����������, ����� 2