"/usr/bin/ld: cannot find -lz"

I am trying to compile Android source code under Ubuntu 10.04. I get an error saying,

/usr/bin/ld: cannot find -lz

Can you please tell me how can I fix it? What does cannot find -lz mean? Here's the full error message:

external/qemu/Makefile.android:1101: warning: overriding commands for target `external/qemu/android/avd/hw-config-defs.h'
external/qemu/Makefile.android:933: warning: ignoring old commands for target `external/qemu/android/avd/hw-config-defs.h'
host SharedLib: libneo_cgi (out/host/linux-x86/obj/lib/libneo_cgi.so)
/usr/bin/ld: skipping incompatible /usr/lib/gcc/i486-linux-gnu/4.4.3/../../../libz.so when searching for -lz
/usr/bin/ld: skipping incompatible /usr/lib/gcc/i486-linux-gnu/4.4.3/../../../libz.a when searching for -lz
/usr/bin/ld: skipping incompatible /usr/lib/libz.so when searching for -lz
/usr/bin/ld: skipping incompatible /usr/lib/libz.a when searching for -lz
/usr/bin/ld: cannot find -lz
collect2: ld returned 1 exit status
make: *** [out/host/linux-x86/obj/lib/libneo_cgi.so] Error 1

And my GCC version output:

scheung@scheung-virtual-box:/media/EXTDIV/mydroid$ gcc --version
gcc (Ubuntu 4.4.3-4ubuntu5) 4.4.3
Copyright (C) 2009 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

I already have the zlib1g-dev library installed:

$ sudo apt-get install zlib1g-dev 
Reading package lists... Done
Building dependency tree       
Reading state information... Done
zlib1g-dev is already the newest version.

(I get that from this link.)

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.

sudo apt-get install zlib1g-dev

I don't need all the x86 libs ;)