Obrigado a @ user535733 pelo útil comment : "Use o dpkg para desinstalar o pacote ofensivo (conflitante), então use o apt para limpar as dependências"
Veja como removi os pacotes conflitantes:
$ sudo dpkg --remove kde-telepathy
(Reading database ... 1330002 files and directories currently installed.)
Removing kde-telepathy (15.04.20ubuntu1) ...
$ sudo dpkg --remove kde-telepathy-minimal
(Reading database ... 1329999 files and directories currently installed.)
Removing kde-telepathy-minimal (15.04.20ubuntu1) ...
Depois eu limpei com
sudo apt autoremove