Та же проблема, была.
Решение:
На сервере в sshd_config добавил строчку
AcceptEnv LANG LC_*
затем
sudo service ssh restart
На клиенте (Windows PuTTY). В сохраненной сессии Connection - Data
Добавил
Environment variables
LANG ru_RU.UTF-8
Вуаля!
UPD:
Самое интересное, что раньше работало, а в какой момент перестало и что я менял - не заметил )))