Parece que você está definindo $ LC_CTYPE em seu .profile ou .bashrc ou qualquer outra coisa. Isso não foi executado antes de seu primeiro terminal, que, portanto, é iniciado sem isso em seu ambiente:
init - (inicia) - > Gestor de visualização - (inicia) - > ambiente de trabalho env - (inicia) - > terminal - (inicia) - > shell
O shell então origina seu arquivo de inicialização (.profile, .bashrc, .zshrc, .login, o que for para o seu shell), que define o ambiente, e somente quando você inicia o terminal, ele sabe quais configurações de localidade é suposto usar.
Você precisa configurar o LC_CTYPE mais acima na cadeia - onde e como, depende do seu ambiente de desktop (espero que você não esteja usando "apenas um gerenciador de janelas", provavelmente gnome ou KDE?), gerenciador de exibição (gdm ou kdm ou xdm ou lightdm ou qualquer outro), variante init (tradicional "sysv-style" ou upstart).