Eu não acho um pacote Python 2.4 para o Ubuntu, então eu suponho que você tentou compilá-lo a partir do código-fonte. Em caso afirmativo, você teria que configurar e compilar explicitamente com suporte ao zlib.
Encontrei um artigo no blog sobre como fazer isso aqui:
basicamente instale o zlib1g-dev e configure o Python com
./configure --with-zlib=/usr/include
então você pode fazer "make" para gerar os binários 2.4 do Python.