Совет в рассылке от 06 апреля:

rm -f /etc/menu-methods/kde-*
update-menus

А также стереть все каталоги tmp в /.kde, выполнить update-menus от пользователя и всё равно не поможет :)