Como jasonwryan sugeriu, foi realmente uma questão local.
O cliente estava usando en_US.UTF-8 , enquanto o servidor estava usando en_US . Não totalmente claro em por que é importante, mas o que quer que funcione.
Para o slackware, para defini-lo globalmente, modifique /etc/profile.d/lang.sh , conforme especificado aqui
Para modificá-lo apenas por usuário, basta definir LANG no seu .bashrc ou qualquer outra coisa.
