Geralmente são problemas de drivers de vídeo. Procure problemas que outras pessoas tiveram com a mesma placa gráfica. Se você estiver usando o driver gráfico gratuito, experimente o proprietário e vice-versa ( radeon / fglrx , nouveau / nvidia ).
O KDE não está relacionado. Pode haver logs interessantes em /var/log/Xorg.0.log e nos logs do kernel, mas se o computador travar ao reiniciar, não terá tempo para salvar nenhum registro.