This is fairly common in KDE 3.2, I suffered it too under FC2 (and other KDE related badness which made me switch back to gnome).
I added Firefox to Kmenu>Internet>Firefox, saved it all fine, and it worked from the menu.
I found that I could add them to the menu and they would stay after a reboot, but once I opened kmenuedit again, it would no longer allow me to expand Internet, so I could not move or rename or add anything further to the Internet menu.
I thought it might be a one off so I decided to explore this and add something else to a different menu, this time Kmenu>Office and again - it would no longer allow me to expand the folder.
I also had problems with Kfind locking whenever I searched for a file (both on a fresh install and after yum updated everything, a problem I had in a previous post).
Wish I'd known to delete ~/.config folder then, and I might have stuck with it!