This one bit me the other day... It appears that python used to install /usr/sbin/python-updater up to version 2.4.4, but in later revs of 2.4.4 (like -r4), it no longer does this and instead PDEPENDs on the python-updater package. But python-updater, if installed, will cause a collision of this file, overwriting the one installed by python. Because portage (2.1.3) now removes orphaned files by default, upgrading python from python-2.4.4 will cause /usr/sbin/python-updater to be removed from the system (assuming python-updater has already been installed (thereby already satisfying python's new dependence on it), which was the case on two of my setups). Now the file will simply mysteriously not exist, and one has to manually re-install python-updater to get it back. A solution would be to add a block of <=python-2.4.4 in python-updater. Or python-updater could RDEPEND on >python-2.4.4.
I just wanted to say that this bug hit me today. Very confusing, because emerge shows python-updater as installed, and qlist -v python-updater aggrees; yet /usr/sbin/python-updater just doesn't exist. I'd bump the priority up a notch on this one, as it is mysterious breakage bound to stress out a lot of users.
Thanks for the report! I've bumped the severity as I agree this is an insidious problem, and the fix is easy.
I've cleaned out redundant versions of python and added a blocker to python-updater for python versions older than 2.3.6-r2. 2.3.6-r2 and newer versions depend on app-admin/python-updater. Thanks for reporting :)