А если
# apt-get remove altlinux-freedesktop-menu-nested-menu
$ kbuildsycoca5 --noincremental
?
Помогло, но теперь программы в менюхах списком, без разбивки по подменюшкам. Это нереально неудобно.
Получается дело в этом altlinux-freedesktop-menu-nested-menu?