Eu acho que o problema é que o python2.6 não foi compilado com o zlib. Eu executei os seguintes comandos e isso consertou meu problema (isso assume que você tem o código fonte do Python 2.6):
apt-get install zlib1g-dev
cd Python-2.6.5
./configure
make
make install
... também há muitas outras coisas com as quais o python construirá. O instalador não irá falhar se eles estiverem faltando, ele apenas construirá sem eles.