Acabamos de encontrar a solução. O problema foi com a configuração do Putty.
"SuperPutty -> Tools -> Putty Configuration -> Windows ->Translation -> Remote Char set"
foi definido como ISO
em vez de UTF8
.
Depois que mudamos o conjunto de caracteres remoto para UTF8, o problema foi corrigido.
Graças a muru e terdon por suas entradas, nos ajudou na busca na direção certa.