Consegui descobrir o que estava errado executando apt-get
com uma opção de depuração:
sudo apt-get -o Debug::pkgProblemResolver=true install -f
Isso mostrou por que o pacote estava sendo removido. No meu caso, apt-get
não conseguiu encontrar uma certa dependência nos repositórios.