Когда-то делал так: <Ctrl>+P (настройки), вкладка "Шрифты". Далее эксперементальным путем меняешь шрифты. Если повезет
- русские названия будут отображаться нормально.
PS: Пробовал сии манипуляции в Knoppix(не помню какой), ALTLinux-4-Desktop, ASPLinux-11, Debian-4. Как оно будет в убунте - не знаю, за отсутствием опыта её использования.