Existem hacks para suporte a terminal unicode, como unicode_start, mas não são perfeitos, conforme indicado na documentação.
Alternativamente, aparentemente o 'fbterm' suporta o Unicode e já existem pacotes para o Debian. Você poderia tentar isso?
link