Eu tive problemas semelhantes com apt-get upgrade
no Ubuntu 10.04. Então aprendi que apt-get dist-upgrade
é melhor em lidar com dependências. Eu usei apt-get dist-upgrade
desde então e funcionou para mim em 10.04, 12.04, 14.04 e 16.04.