ntc2 é essencialmente correto (no meu caso, de qualquer forma), mas permita-me elaborar sobre a solução.
Por alguma razão, eu estava preso em 15.04, embora tenha sido configurado para atualização automática. Não importa quantas vezes eu atualizei / atualizei nenhuma nova versão estava sendo mostrada, e continuei recebendo o erro de autenticação ao instalar pacotes.
No entanto, eu finalmente descobri como forçar a atualização através das Notas de Lançamento oficiais do Ubuntu 15.10 (Wily Werewolf).
Acaba por ser bastante simples, e no meu caso tudo o que eu realmente precisava era o último passo.
Atualizando do Ubuntu 15.04:
% bl0ck_qu0te%
Agora que atualizei o erro de autenticação, resolvi e posso instalar pacotes sem problemas.
Problema de atualização - E: o método deu 103 mensagem de redirecionamento inválida
Isso pode ou não estar relacionado aos problemas de atualização, por isso deixarei isso aqui, caso alguém mais também encontre isso.
Se durante a atualização você encontrar o seguinte erro:
% bl0ck_qu0te%
Você pode ter que limpar os arquivos parciais com o abaixo e tentar novamente a atualização:
sudo rm /var/lib/apt/lists/partial/*
(Fonte: link )
Esta foi a peça final para fazer a atualização passar por mim.