As configurações de codificação de localidade são utf8 em vez de UTF-8 .
experimente este comando:
sudo locale-gen en_CA.UTF-8
saia do terminal e faça o login novamente (não sei se você precisa reinicializar).
Verifique se as configurações do local estão corretamente modificadas e tente o comando perl e apt-get.