Eso es muy raro
¿hiciste una instalación por defecto? ¿qué tan completa fue?
¿te pasa si usás Alt-F2? ("ejecutar")
¿te pasa con todas las terminales? (probá ejecutar "xterm")
¿Qué pasa si estás en xterm e intentás ejecutar "konsole"?
El comportamiento que describís es muy extraño...
Saludos.