When using the installer (e.g., from DVD) to upgrade from a previous version of Fedora, packages that are part of the default install in the new version, but were not part of previous versions, are generally not installed. This causes users who upgrade but don't manually go through and add packages to miss many of the new features in the new version. (And, frankly, it's one of the reasons that installing and using Fedora isn't something that the average user can do properly.) What I've done through many previous upgrades is go through comps.xml, figure out which groups are part of what I install, and add all the packages that are mandatory or default in those groups. But I really shouldn't have to do this. Instead, the installer should have some notion of what groups I've chosen to install and should add, or at least offer to add, the new packages available in those groups. In Fedora Core 5, some of these packages were a pretty big deal, such as gnome-power-manager, hplip, and beagle, among others. In Fedora Core 3, they included the SELinux packages, bluez-*, prelink, redhat-lsb, and rhgb. (I've done similar things for other upgrades, but didn't save the list.) Users who upgrade shouldn't miss the important new features, but by default they often do.
An upgrade fundamentally cannot provide an identical experience to a fresh install as there are some things which have to be done at filesystem creation time. We pull in packages that are required, but going beyond that is hard. Think about the case where a user, eg, removes something like the bluetooth utilities because they don't have bluetooth hardware. Having that come back every time they do an upgrade is also not good. So there's not really a way to do this that doesn't have downsides.
If the goal is to have an operating system that normal people can use, then you may have to sacrifice some of the things geeks want. Frankly, though, I think this use case is much more important than not reinstalling a single package that the user removed. And if the user removed a large group of packages, maybe there's a deficiency in the package grouping? I'd agree that it may be hard to fix this bug well, but I disagree that that means nobody should try. There are lots of sources of useful information to do this well: the history of what the user originally installed and how they selected that set (e.g., accepting defaults or picking packages), what they added/removed, what proportion of each group in the old version is currently installed on the system, how the installation defaults changed between versions, etc.