В /etc/menu-methods/lang.h или /etc/menu-methods/menu.h для lang() и languages() прописать кодировку, например: function lang()=ru_RU.KOI8-R"" function languages()="ru_RU.KOI8-R" Из-под root запустить: update-menus
dpkg --search update-menus menu: /usr/share/man/man1/update-menus.1.gz menu: /usr/bin/update-menus menu: /usr/share/man/fr/man1/update-menus.1.gz