Portanto, a solução foi muito fácil, afinal. Reconfigurar o xserver ou o KDE não ajudou a desinstalar o xserv-xorg sozinho também não teve efeito. Mas remover todos os pacotes xorg e xserver e remover completamente os drivers do ati e depois instalar os novos drivers ati com um novo xserv funcionou bem (além do fato de que eu tive que construir a versão do Ubuntu dos debs, mas tudo bem parece funcionar ).
Parece que o processo de atualização não funcionou bem com o driver da ati e com a versão do meu xserver - bem, provavelmente apenas com os drivers da ati.