After checking to which package does the libz.so.1 belongs (http://packages.ubuntu.com/lucid/i386/zlib1g/filelist) you should try to install zlib1g:
sudo apt-get install zlib1g
As pointed by @E-rich, it may be required to add a :i386 suffix to the package name for the package manager correctly identify it:
sudo apt-get install zlib1g:i386
EDIT (for CentOS or other distro that makes use of yum):
If someone using CentOS (or any other distro that makes use of yum) that may end up reading this question, @syslogic proposed the following solution in the comments:
yum install zlib.i686
or, for 32-bit binaries:
yum install zlib.i386