A saída que você forneceu em apt-cache policy
confirma minha suspeita sobre listas desatualizadas.
Para o exemplo de krb5-multidev
em 12.04, você deve ver a versão 1.10+dfsg~beta1-2ubuntu0.3
como candidata fornecida por precise-updates
.
krb5-multidev:
Installed: 1.10+dfsg~beta1-2ubuntu0.3
Candidate: 1.10+dfsg~beta1-2ubuntu0.3
Version table:
*** 1.10+dfsg~beta1-2ubuntu0.3 0
500 http://nl.archive.ubuntu.com/ubuntu/ precise-updates/main amd64 Packages
500 http://security.ubuntu.com/ubuntu/ precise-security/main amd64 Packages
100 /var/lib/dpkg/status
1.10+dfsg~beta1-2 0
500 http://nl.archive.ubuntu.com/ubuntu/ precise/main amd64 Packages
Então, como já sugeri nos comentários, corra
sudo apt-get update
E você deve estar pronto (tente novamente a instalação e também atualize seu sistema corretamente!).