Странно, у меня после установки все в UTF8 было нормально...
Да, для поддержки терминуса иксами надо было еще в /etc/fonts/local.conf раскомментировать <dir>/usr/X11R6/lib/X11/fonts</dir> - поключение растовых шрифтов
Если бы ты посмотрел на офф. сайте (даже можно на русском зеркале: www.ubuntu-ru.org), поискал бы в форуме, то предлагались аж 2 метода русификации. Один заключался в прописании верного кириллического шрифта для консоли (SCREEN_FONT=Cyr_a8x16 в /etc/console-tools/config, APP_CHARSET_MAP=utf8), другой - всего лишь в установке 2-3 пакетов. Сделай apt-get install console-cyrillic, он сам все, что нужно поставит.
Гадость этот ru-utf (равно как и ua-utf и ua-utf-ws). Попробуй в (почти) любой программе, не использующей readline (в том числе когда вводишь логин и пароль) ввести что-то и нажать BackSpace (стереть можно только ^U и кажется ^W). С другими раскладками всё OK.