I had the exact same error, and like you, installing zlib1g-dev did not fix it. Installing lib32z1-dev got me past it. I have a 64 bit system and it seems like it wanted the 32 bit library.
For x64 install zlib1g-dev.
zlib1g-dev
sudo apt-get install zlib1g-dev
I don't need all the x86 libs ;)
sudo apt-get install libz-dev in ubuntu.
sudo apt-get install libz-dev