Se você fizer um "rpm -qa | grep zlib", o que você ganha? Pode ser uma questão de ter que
yum install zlib zlib-devel zlib-static
Isso garantirá que você tenha todos os pacotes necessários. Se você tiver todos esses, talvez seja necessário criar um link simbólico onde sua versão atual do zlib e suas bibliotecas estão para onde o Python está procurando por eles. Ou especifique na configuração do Python onde seus arquivos zlib estão.
Disclaimer: Eu não instalei o Python 2.7.3 especificamente, mas normalmente é o problema com esses tipos de erros na minha experiência.