I ran into the same problem with KDE on 2 different computers. The problem is a bug in RPM. You need to update RPM before you install/update any other software. Here are the particulars:
Size: 4819 KB
Summary: The RPM package management system
Cause:A bug was found in the way that rpm locks it's database in that it prevents update-menus from running properly and can cause the loss of KDE, GNOME, and other WM menus.
This package provides a better locking mechanism that should prevent this improper behaviour.
Description: RPM is a powerful command line driven package management system capable of installing, uninstalling, verifying, querying, and updating software packages. Each software package consists of an archive of files along with information about the package like its version, a description, etc.
In order to get your menus back, run
as root. This worked on one of the computers & tried it on but not the other. Good luck.