Aba
На фре-клиенте С, на линухе-клиенте utf8, на фре- серваке utf8
Из своего опыта заметил, что перекодировки из простых, старых локалей в utf8 работают без косяков. А обратно бывают нестыковки. То есть, если на серваке системная локаль будет С, а пользовательские например, cp1251, то putty со screen на utf8 заработает.
Попробуйте так.