Bom, já que você falou em atualização do KDE, tente isso:
1 - Tecle simultaneamente Crtl+Alt+F1
2 - No terminal, logue com seu usuário e senha (não estranhe se não aparecer nada na tela enquanto você tecla a senha)
3 - Execute: sudo apt-get -f install
Se tiver opção S/n, tecle s e enter.
Explicando: se você não solicitou a instalação do metapacote kde, alguns arquivos importantes podem ter ficado de fora, como é o caso do kdelibs. Caso a dica anterior não funcione, tente:
sudo apt-get install kdelibs
que deve funcionar. Boa sorte!