Eu tive o mesmo problema ao tentar atualizar de 12.04 para 12.10. A questão parece ser que os repositórios "natty-backports" não estão funcionando corretamente. Se você desativá-los, o problema será resolvido.
Para isso, edite o arquivo /etc/apt/sources.list diretamente.
De um terminal:
sudo gedit /etc/apt/sources.list
em seguida, comente as duas linhas que contêm "natty-backports". Linhas 34 e 35, eu acho.
Salve e tente executar a atualização novamente. Você pode ter que fazer um manual "verificar se há atualizações".
Espero que funcione para você!