I've done this a few times in a few different ways. You definitely don't want to try to "upgrade" to a different distribution. Even when Mandake first diverged from Red Hat it was a bad idea, and almost certain to result in an unusable system.
The other thing is that Ubuntu uses a different package tracking system than Red Hat/Fedora, it doesn't use RPM, so it wouldn't be able to tell if anything were installed in the first place, and would most likely do a new install over the existing one, possibly leaving unused cruft all over the place. Ubuntu puts files in different places too, so you could end up with a real mess. (Of course, it's possible that the installer script is smart enough to deal with this, but I wouldn't trust it.)
If your system and /home partitions are different, it's usually a good idea to not just delete the system files, but to go ahead and format the system partitions. No idea why, but I've seen that make a difference for an upgrade within the same distro.
Besides backing up your /home directory, you might have things in /var/spool, like /var/spool/mail if you're running an MTA (sendmail, postfix).
It's also a good idea to do "rpm -Va" and back up any configuration files that have been changed from the original, so you can preserve any customizations you made. (If you haven't made any important changes to the system, you can skip that part.)
If you want to stay within the RPM universe and have a familiar operating system and structure, I would strongly recommend Mandriva 2007 (not Mandriva One). Network installs are a breeze if you have broadband and are quicker than downloading and burning the iso's. Mandriva has a LOT more software available than Fedora, and regularly makes backports of updated software packages, not just patches to the existing version. Their urpm* console-based package management system is great, and it's pretty easy to configure it for a good mirror (though it may take some trial and error to find a good one). Version upgrades within Mandriva are working extremely well.
I've run RedHat (from 2.1 - FC4), Mandrake/Mandriva from fairly early on, and I've recently tried Gentoo and Kubuntu, and for a desktop I'd pick Mandriva every time. It's been what I've used since I switched to a Linux desktop about four years ago, with a brief excursion into SuSE. (That's another RPM/SysV/RedHat based system, but I don't recommend it for non-commercial users.)
(That said, I wouldn't recommend Mandriva, especially 2007, for a server. Next one's going to be Ubuntu LTS.)