Uso o 12.10 e tive exatamente o mesmo estranho problema há 2 dias. Tentei de tudo, até copiei o /etc/apt/sources.list de outra máquina mas nada resolveu.
Me lembrou a desagradável sensação de "pegar" vírus, que já tinha esquecido nos 5 anos usando Mandriva e 6 meses com o Mageia Linux.
Como não encontrei nenhuma solução pensei que o problema foi só comigo, algum arquivo corrompido ou coisa do gênero, decidi formatar e o problema por enquanto não voltou.