sudo rmdir /usr/lib/python2.6/dist-packages/setuptools.egg-info
sudo apt-get install --reinstall python-setuptools
This replaces the empty directory
/usr/lib/python2.6/dist-packages/setuptools.egg-info with a symlink to /usr/share/pyshared/setuptools.egg-info which is a file, not a directory.
Why did I have an empty directory there? Something left remaining from an older python-setuptools package? This system is not a fresh Lucid install; it was upgraded from Karmic (which did not spew any UserWarnings). AFAIK dpkg itself doesn't handle transitions from directories to symlinks. Shouldn't python-setuptools ship a postinst script to correct this during upgrades?