Eu não sei muito sobre o gnome-terminal, mas se você estiver indo trabalhar com scripts não-latinos, você pode querer olhar rxvt-unicode . Ele manipula quase todos os scripts corretamente (desde que você tenha as fontes e a saída seja realmente UTF-8).
$ sudo apt-get install rxvt-unicode
$ urxvt
Como bônus, você obterá uma boa documentação sobre os terminais que podem ser acessados por man 7 urxvt
que também é um bom local para procurar informações sobre solução de problemas.
Note que na configuração padrão o Rxvt parece bastante desagradável (ele tenta ser bom para os usuários do xterm :)) então pesquise na Internet ou no FAQ mencionado sobre como fazer com que pareça melhor.
Outra tarefa é selecionar a fonte correta. Para Urxvt, é font
resource. Para experimentar, você pode especificar o nome da fonte na linha de comando, por ex. 'urxvt-fn "xft: Dejavu Serif". Consulte a documentação do urxvt para isso.
Se você quiser procurar por fontes, eu começarei pesquisando em seu repositório. Por exemplo, aptitude search arabic
ou apt-cache search arabic
faz isso no Debian.