Well I don't know how to resolve your problem properly. Though when I experienced problems that are similar to that (when I first started), I just used to take the "windowsesque" route and re-install.
You don't need to uninstall or re-format as such. Just boot the CD and when it gets to the part about using the same partitions, click yes, then make sure that the partition that it's going to is checked for reformat after that. If you're dual booting make sure you don't check the use entire hard-drive (if you have everything on the one hard drive). It will then install "afresh" over the top.
Also, you can either try doing the updates when the install asks you, but I've found that too be problematic. I always say no to that one, then when it's up and running I add the updates, main, config, jpackage and both plf repositories. I then get rid of the CD ones listed via the mandriva control centre (configure my computer), but when I actually get to run the updater, I do a few packages at a time, otherwise if theres any kind of conflict (when you do a load of packages or all of them at once) it errors you out, which can be a pain if you have 50+ packages to update and it's downloading the 49th one.
Another handy hint. Have at least 3 partitions - I use 4. First /boot, and it should know when installing too put the boot stuff there, a /swap for, well, swap space, a / for the root stuff and main package install and a /home for all your personal stuff/data/customisations etc etc. That way, if you do need to install a different distro or just a newer version of what you have (mandriva 2006 is the current version and thats 2 versions newer than 10.1) you just tell the installer to format/install to the /boot and /, nothing else is touched and as long as you install all the same packages (newer versions withstanding), when you boot it, it should just work with all the icons/shortcuts/packages/customisations (if you installed the packages for them) and any data/address books etc will still be untouched.
You can, of course, just use 3 partitions, I just use a /boot as it's a hangover from when I was using Gentoo. the 3 partition setup would be /swap, / and /home (/ = root of course).