Сейчас долго и вдумчиво тупил над одним странным обстоятельством.
Я (и мои пользователи-клиенты) привык к тому, что на серверах стоит английская система. И, само собой, в этой системе по ssh можно печатать по-русски. К тому же, это удобно — можно держать универсальные образы для английских и русских клиентов.
В первую очередь, само собой, проблема касается OpenVZшных образов.
Сиё делается тремя командами:
root@server:~# locale-gen ru_RU.UTF-8
root@server:~# locale-gen en_US.UTF-8
В Debian можно просто раскомментировать нужные локали в /etc/locale.gen и запустить команду locale-gen без параметров.
Далее выставляем LC_MESSAGES:
root@server:~# update-locale LANG=ru_RU.UTF-8 LC_MESSAGES=POSIX

Этого достаточно. Проверялось при сборке кастомных образов из OpenVZшных официальных версий 8.04, 10.04, 11.04.
Так же эти действия пофиксят проблему с ошибками вида:
locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_ALL to default locale: No such file or directory