Смена locale в системе Debian осуществляется командой:
# dpkg-reconfigure locales
В появившемся интерфейсе необходимо выбрать те, которые Вам нужны, например: ru_RU.UTF-8 UTF-8, ru_RU.KOI8-R KOI8-R.
На Debian 6 встретили баг, иногда локаль не меняется. Поэтому в ~/.profile юзеров я добавил:
export LANG=ru_RU.utf8
Так же добавил в /etc/skel/.profile, что бы новые юзера сразу получали нужную локаль.