При первом логине ввел locale-gen ru_RU.UTF-8
Сразу хотелось уточнить: а ребут системы делали?