Parece que há algo errado com sua configuração perl. Tente o comando sudo dpkg-reconfigure perl-base
e tente o apt-get novamente. Se isso não funcionar, por favor poste a saída de ambos os comandos aqui.
Editar
Com base na sua resposta - sua instalação do Perl está faltando arquivos essenciais e isso está impedindo que o gerenciador de pacotes a conserte.
Já tentou instalar o perl a partir do código-fonte ou algo semelhante?
Preciso de mais informações:
- Qual é a sua versão do Ubuntu:
cat /etc/issue
- Qual é a sua arquitetura:
uname -a
- O que está no diretório perl do seu sistema:
ls -l /usr/share/perl
Verifique também esta resposta e veja se de alguma forma o seu programa perl está olhando para o lugar errado.
Além disso, tente criar um novo usuário com direitos sudo, faça o logon como novo usuário e tente novamente, caso o problema seja específico do usuário, e não de todo o sistema.