Today I fixed my ubuntu 8.10 installation, where above error occured, whenever I wanted to upgrade the system. It occured while upgrading the python2.5-minimal package.

The failure originated from the python-setuptools and the following (simple) commands fixed it cleanly:

sudo dpkg -r python-setuptools
sudo apt-get install python-setuptools

Cheers, iss