O problema foi resolvido depois de executar sudo apt-get dist-upgrade .
O que isso faz?
Da página de manual apt-get :
dist-upgrade, além de executar a função de atualização, também lida de maneira inteligente com as novas dependências, com novas versões de pacotes;apt-gettem um sistema de resolução de conflitos "inteligente" e ele tentará atualizar os pacotes mais importantes no despesas de menos importantes, se necessário. O código% comando pode, portanto, remover alguns pacotes.