Os comandos do companheiro acima podem não resolver, mas que serão imprescindíveis para que você mostrando a saída do sudo apt-get update ao fórum possa ser analisado melhor seu problema.
Ou então tente assim:
sudo rm /var/lib/apt/lists/* ; sudo rm /var/lib/apt/lists/partial/* ; sudo apt-get -f install ; sudo apt-get clean ; sudo apt-get update
T+
Obrigado.
Foi o único que resolveu o meu problema depois de horas e horas de pesquisa...
Foi batata depois deste comando, devido à um erro de instalação do Azureus Vuze no Ubuntu 12.04.