Natty has introduced a new feature called multiarch. Some shared libraries are installed in architecture specific directories, e.g. /usr/lib/x86_64-linux-gnu/libz.so instead of /usr/lib/libz.so. The dynamic linker ld.so has been modified to look for libraries in the new locations. If you wonder how, /etc/ld.so.conf.d/x86_64-linux-gnu.conf does the trick. However Python's setup.py uses hard coded paths and doesn't know about the new feature. Barry's posting  has some insight information.
The problem has been dealt with for Python 2.7, 3.1, 3.2 and newer versions, but 2.6 and earlier won't see any fixes. Current Python releases (2.7.1, 3.2.0) suffer from the issue, too. Don't be battle-weary! The solution to the issue is rather simple.
$ make distclean
$ export LDFLAGS="-L/usr/lib/$(dpkg-architecture -qDEB_HOST_MULTIARCH)"
$ make install
$ unset LDFLAGS
This adds an additional library search path (-L/usr/lib/x86_64-linux-gnu on my box). Now setup.py knows about the multiarch lib directory and builds zlib and all the other missing modules just fine.
Actually my build system a bit more paranoid. It also adds /lib/x86_64-linux-gnu as library search path and /usr/include/x86_64-linux-gnu as header include path for C and C++.
$ export arch=$(dpkg-architecture -qDEB_HOST_MULTIARCH)
$ export LDFLAGS="-L/usr/lib/$arch -L/lib/$arch"
$ export CFLAGS="-I/usr/include/$arch"
$ export CPPFLAGS="-I/usr/include/$arch"
$ make install
$ unset arch LDFLAGS CFLAGS CPPFLAGS