Here is the output of make when it fails:

Making all in .
make[2]: Entering directory `/usr/src/rpm-3.0.4'
/bin/sh ./libtool --mode=link gcc -g -O2 -D_GNU_SOURCE -Wall -Wpointer-arith -Wstrict-prototypes -Wmissing-prototypes -Wno-char-subscripts -all-static -L./build -L./lib -L./popt -o rpm2cpio  rpm2cpio.o ./build/.libs/librpmbuild.a      ./lib/.libs/librpm.a    ./popt/.libs/libpopt.a       -L/usr/local/lib -ldb1 -lz -lbz2
gcc -g -O2 -D_GNU_SOURCE -Wall -Wpointer-arith -Wstrict-prototypes -Wmissing-prototypes -Wno-char-subscripts -static -L./build -L./lib -L./popt -o rpm2cpio rpm2cpio.o ./build/.libs/librpmbuild.a ./lib/.libs/librpm.a ./popt/.libs/libpopt.a -L/usr/local/lib -ldb1 -lz -lbz2
/usr/i686-pc-linux-gnu/bin/ld: cannot find -lz
collect2: ld returned 1 exit status
make[2]: *** [rpm2cpio] Error 1
make[2]: Leaving directory `/usr/src/rpm-3.0.4'
make[1]: *** [all-recursive] Error 1
make[1]: Leaving directory `/usr/src/rpm-3.0.4'
make: *** [all-recursive-am] Error 2

configure did not complain about -lz (I'm guessing that's zlib). There
were no problems up to this point either. I'm using zlib-1.1.3.
Any ideas?