Running anaconda to upgrade from an updated FC3 system to FC4 leaves the system in a half-upgraded state, because FC3's updated kernel has a higher version number (2.6.12) than FC4's kernel (2.6.11). I filed bug 172917 on anaconda, but the maintainer says that anaconda is working as designed and that each individual package must keep its version number lower than that in newer distros.
One day, Anaconda will have the ability to install packages from multiple repositories during the installation, at which point the latest updates for the release being installed should supercede any updates that may have been already installed on the previous distro. This requires quite a bit to change in Anaconda though aparently, so it's likely this won't be seen until FC6 at the soonest. Jeremy, I'm reassigning this back as an anaconda bug, as theres really not anything I can do here other than either - Never update the kernel past the release that shipped (And forego lots of updates) or - Munge the version number to lie, and pretend its younger than it actually is. This sounds like such a bad idea I'm hating myself for even suggesting it.
Fedora Core 3 is now maintained by the Fedora Legacy project for security updates only. If this problem is a security issue, please reopen and reassign to the Fedora Legacy product. If it is not a security issue and hasn't been resolved in the current FC5 updates or in the FC6 test release, reopen and change the version to match. Thank you!