I had a similar problem as spineynorman. I am using MDK 9.1 and ran MandrakeUpdate (from the KDE Menus). One of the updates wanted to uninstall some programs. I figured that they would be reinstalled when they were done a certain update. I assumed too much there.
I tried to rebuild my menus, I found that in the forums here, but that seemed to only get as far as trying to rebuild the simplified Gnome menus and just sort of sat there.
After I got rpmdrake re-installed I tried Mandrakeupdate again. The update for coreutils is what wants to uninstall about 6 files/programs. I did not let it do that this time. I then tried urpmi but it wanted to do the same thing.
(I got the missing rpm's off of MDK CD1 and installed from the hardrive with Kpackage. I also downloaded some of the rpms from RPMPBone).
I then downloaded and used Kpackage for the coreutils rpm from RPMPBone. I was not prompted to uninstall anything. My menus seemed to be intact. I then ran Mandrakeupdate and I was up to date!
Hopefully this will help others resolve this problem quickly.