Sugira o seguinte
sudo apt-get clean
então
sudo apt-get update
então
sudo apt-get install openjdk-6-jre
A partir da página man: "limpa limpa o repositório local de arquivos de pacotes recuperados. Ele remove tudo, exceto o arquivo de bloqueio de / var / cache / apt / archives / e / var / cache / apt / archives / partial /."
Se isso não resolver seu problema, poste o conteúdo de /etc/apt/sources.list
(EDIT): Seu sources.list parece bem. Tente sudo apt-get install -f && apt-get install openjdk-6-jre
. O sinalizador -f para o apt-get install significa 'Fix', isto é, tenta corrigir um sistema com dependências quebradas no lugar. Esta opção, quando usada com install / remove, pode omitir quaisquer pacotes para permitir que o APT deduza uma solução provável.