В /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