Eu estava com o mesmo erro. A tentativa de instalar o kde-config-telepathy-accounts apenas deu outra mensagem de erro.
sudo apt-get autoremove -f kde-telepathy*
corrigiu o problema removendo forçosamente os pacotes ofensivos e dando-me novamente o controle do apt.