I installed Debian 3.1 just so that I could build OpenWrt. I ran svn to get the code and ran make menuconfig (not changing anything) then ran make. It crunched for a long time then died with this error:

[output snipped]
make -C lzma prepare
make[2]: Entering directory `/root/openwrt/whiterussian/openwrt/target/lzma'
/root/openwrt/whiterussian/openwrt/scripts/download.pl /root/openwrt/whiterussian/openwrt/dl lzma406.zip a09378411cba5f786b5c49c9c58496df http://www.7-zip.org/dl
--01:24:33--  http://www.7-zip.org/dl/lzma406.zip
           => `-'
Resolving www.7-zip.org... 69.73.175.23
Connecting to www.7-zip.org[69.73.175.23]:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 185,934 [application/zip]

100%[================================================================================================>] 185,934       --.--K/s

01:24:33 (9.81 MB/s) - `-' saved [185934/185934]

unzip -q /root/openwrt/whiterussian/openwrt/dl/lzma406.zip -d /root/openwrt/whiterussian/openwrt/build_mipsel/lzma
patch -d /root/openwrt/whiterussian/openwrt/build_mipsel/lzma -p1 < lzma-406-zlib-stream.patch
patching file SRC/7zip/Compress/LZMA/LZMADecoder.cpp
patching file SRC/7zip/Compress/LZMA/LZMADecoder.h
patching file SRC/7zip/Compress/LZMA_Lib/makefile
patching file SRC/7zip/Compress/LZMA_Lib/ZLib.cpp
touch /root/openwrt/whiterussian/openwrt/build_mipsel/lzma/.unpacked
make[2]: Leaving directory `/root/openwrt/whiterussian/openwrt/target/lzma'
make -C lzma compile
make[2]: Entering directory `/root/openwrt/whiterussian/openwrt/target/lzma'
make -C /root/openwrt/whiterussian/openwrt/build_mipsel/lzma/SRC/7zip/Compress/LZMA_Lib
make[3]: Entering directory `/root/openwrt/whiterussian/openwrt/build_mipsel/lzma/SRC/7zip/Compress/LZMA_Lib'
g++ -O3 -Wall -c ZLib.cpp
ZLib.cpp:28:18: zlib.h: No such file or directory
ZLib.cpp:53: error: parse error before `*' token
ZLib.cpp:54: error: missing ';' before right brace
ZLib.cpp:56: error: ISO C++ forbids defining types within return type
ZLib.cpp:56: error: destructors must be member functions
ZLib.cpp:56: error: return type specification for destructor invalid
ZLib.cpp:56: error: virtual outside class declaration
ZLib.cpp:58: error: virtual outside class declaration
ZLib.cpp: In function `LONG QueryInterface(const GUID&, void**)':
ZLib.cpp:58: error: invalid use of `this' in non-member function
ZLib.cpp:58: error: `AddRef' undeclared (first use this function)
ZLib.cpp:58: error: (Each undeclared identifier is reported only once for each
   function it appears in.)
ZLib.cpp:58: error: invalid use of `this' in non-member function
ZLib.cpp: At global scope:
ZLib.cpp:58: error: virtual outside class declaration
ZLib.cpp: In function `ULONG AddRef()':
ZLib.cpp:58: error: `ULONG AddRef()' used prior to declaration
ZLib.cpp:58: error: `__m_RefCount' undeclared (first use this function)
ZLib.cpp: At global scope:
ZLib.cpp:58: error: virtual outside class declaration
ZLib.cpp: In function `ULONG Release()':
ZLib.cpp:58: error: invalid use of `this' in non-member function
ZLib.cpp: At global scope:
ZLib.cpp:61: error: virtual outside class declaration
ZLib.cpp: In function `LONG Read(void*, unsigned int, UInt32*)':
ZLib.cpp:62: error: `m_size' undeclared (first use this function)
ZLib.cpp:62: error: `m_offset' undeclared (first use this function)
ZLib.cpp:66: error: `m_data' undeclared (first use this function)
ZLib.cpp: At global scope:
ZLib.cpp:78: error: virtual outside class declaration
ZLib.cpp:83: error: virtual outside class declaration
ZLib.cpp:103: error: virtual outside class declaration
ZLib.cpp:107: error: parse error before `protected'
ZLib.cpp:109: error: `UInt64 m_size' used prior to declaration
ZLib.cpp:110: error: `UInt64 m_offset' used prior to declaration
ZLib.cpp:111: error: parse error before `}' token
ZLib.cpp:118: error: parse error before `*' token
ZLib.cpp:119: error: missing ';' before right brace
ZLib.cpp:120: error: ISO C++ forbids defining types within return type
ZLib.cpp:120: error: destructors must be member functions
ZLib.cpp:120: error: return type specification for destructor invalid
ZLib.cpp:120: error: virtual outside class declaration
ZLib.cpp:122: error: virtual outside class declaration
ZLib.cpp: In function `LONG QueryInterface(const GUID&, void**)':
ZLib.cpp:122: error: redefinition of `LONG QueryInterface(const GUID&, void**)'
ZLib.cpp:58: error: `LONG QueryInterface(const GUID&, void**)' previously
   defined here
ZLib.cpp:122: error: redefinition of `LONG QueryInterface(const GUID&, void**)'
ZLib.cpp:58: error: `LONG QueryInterface(const GUID&, void**)' previously
   defined here
ZLib.cpp:122: error: invalid use of `this' in non-member function
ZLib.cpp: At global scope:
ZLib.cpp:122: error: virtual outside class declaration
ZLib.cpp: In function `ULONG AddRef()':
ZLib.cpp:122: error: redefinition of `ULONG AddRef()'
ZLib.cpp:58: error: `ULONG AddRef()' previously defined here
ZLib.cpp:122: error: redefinition of `ULONG AddRef()'
ZLib.cpp:58: error: `ULONG AddRef()' previously defined here
ZLib.cpp: At global scope:
ZLib.cpp:122: error: virtual outside class declaration
ZLib.cpp: In function `ULONG Release()':
ZLib.cpp:122: error: redefinition of `ULONG Release()'
ZLib.cpp:58: error: `ULONG Release()' previously defined here
ZLib.cpp:122: error: redefinition of `ULONG Release()'
ZLib.cpp:58: error: `ULONG Release()' previously defined here
ZLib.cpp:122: error: invalid use of `this' in non-member function
ZLib.cpp: At global scope:
ZLib.cpp:125: error: virtual outside class declaration
ZLib.cpp: In function `LONG Write(const void*, unsigned int, UInt32*)':
ZLib.cpp:126: error: `m_maxsize' undeclared (first use this function)
ZLib.cpp: At global scope:
ZLib.cpp:145: error: virtual outside class declaration
ZLib.cpp:150: error: virtual outside class declaration
ZLib.cpp: In function `LONG Seek(long long int, unsigned int, UInt64*)':
ZLib.cpp:150: error: redefinition of `LONG Seek(long long int, unsigned int,
   UInt64*)'
ZLib.cpp:83: error: `LONG Seek(long long int, unsigned int, UInt64*)'
   previously defined here
ZLib.cpp:150: error: redefinition of `LONG Seek(long long int, unsigned int,
   UInt64*)'
ZLib.cpp:83: error: `LONG Seek(long long int, unsigned int, UInt64*)'
   previously defined here
ZLib.cpp: At global scope:
ZLib.cpp:170: error: virtual outside class declaration
ZLib.cpp:176: error: parse error before `protected'
ZLib.cpp:178: error: redefinition of `UInt64 m_size'
ZLib.cpp:109: error: `UInt64 m_size' previously declared here
ZLib.cpp:179: error: `UInt64 m_maxsize' used prior to declaration
ZLib.cpp:180: error: redefinition of `UInt64 m_offset'
ZLib.cpp:110: error: `UInt64 m_offset' previously declared here
ZLib.cpp:181: error: parse error before `}' token
ZLib.cpp:183: error: syntax error before `int'
ZLib.cpp:188: error: `inStreamSpec' was not declared in this scope
ZLib.cpp:190: error: syntax error before `*' token
ZLib.cpp:191: error: `outStreamSpec' was not declared in this scope
ZLib.cpp:211: error: parse error before `for'
ZLib.cpp:211: error: parse error before `;' token
ZLib.cpp:211: error: syntax error before `++' token
ZLib.cpp:213: error: syntax error before `.' token
ZLib.cpp:214: error: syntax error before `.' token
ZLib.cpp:215: error: syntax error before `.' token
ZLib.cpp:216: error: syntax error before `.' token
ZLib.cpp:217: error: syntax error before `.' token
ZLib.cpp:218: error: syntax error before `.' token
ZLib.cpp:220: error: syntax error before `.' token
ZLib.cpp:221: error: syntax error before `.' token
ZLib.cpp:223: error: syntax error before `.' token
ZLib.cpp:224: error: syntax error before `.' token
ZLib.cpp:230: error: parse error before `if'
ZLib.cpp:240: error: syntax error before `->' token
ZLib.cpp:241: error: ISO C++ forbids declaration of `destLen' with no type
ZLib.cpp:241: error: invalid conversion from `UInt64' to `int*'
ZLib.cpp:243: error: parse error before `return'
ZLib.cpp:246: error: syntax error before `int'
ZLib.cpp:250: error: redefinition of `CMyComPtr<ISequentialInStream> inStream'
ZLib.cpp:188: error: `CMyComPtr<ISequentialInStream> inStream' previously
   declared here
ZLib.cpp:250: error: `inStreamSpec' was not declared in this scope
ZLib.cpp:252: error: syntax error before `*' token
ZLib.cpp:253: error: redefinition of `CMyComPtr<ISequentialOutStream> outStream
   '
ZLib.cpp:191: error: `CMyComPtr<ISequentialOutStream> outStream' previously
   declared here
ZLib.cpp:253: error: `outStreamSpec' was not declared in this scope
ZLib.cpp:259: error: parse error before `if'
ZLib.cpp:262: error: redefinition of `UInt64 fileSize'
ZLib.cpp:239: error: `UInt64 fileSize' previously declared here
ZLib.cpp:264: error: parse error before `if'
ZLib.cpp:269: error: syntax error before `->' token
ZLib.cpp:270: error: ISO C++ forbids declaration of `destLen' with no type
ZLib.cpp:270: error: redefinition of `int*destLen'
ZLib.cpp:241: error: `int*destLen' previously declared here
ZLib.cpp:270: error: invalid conversion from `UInt64' to `int*'
ZLib.cpp:272: error: parse error before `return'
make[3]: *** [ZLib.o] Error 1
make[3]: Leaving directory `/root/openwrt/whiterussian/openwrt/build_mipsel/lzma/SRC/7zip/Compress/LZMA_Lib'
make[2]: *** [/root/openwrt/whiterussian/openwrt/build_mipsel/lzma/SRC/7zip/Compress/LZMA_Lib/liblzma.a] Error 2
make[2]: Leaving directory `/root/openwrt/whiterussian/openwrt/target/lzma'
make[1]: *** [lzma-compile] Error 2
make[1]: Leaving directory `/root/openwrt/whiterussian/openwrt/target'
make: *** [target/compile] Error 2

Clearly, zlib.h is not really missing, so I assume that I have missed something obvious. Any ideas?

I had the same problem.
Compiling on the pre-packaged Fedora-fc5-i386, running under VMWare Player.
Since this is not really meant as a development installation, I had to install a lot of extra software.
Fortunately, this is easy with the yum command line tool.
The problem with zlib.h disappeared after I installed zlib-devel.i386 with this command:

yum install zlib-devel.i386

Next problem that I am facing is compile error in iptables:

/openwrt/whiterussian/openwrt/staging_dir_mipsel/bin/mipsel-linux-uclibc-gcc -Os -pipe -mips32 -mtune=mips32 -funit-at-a-time  -Wall -Wunused -I/openwrt/whiterussian/openwrt/build_mipsel/linux/include -Iinclude/ -DIPTABLES_VERSION=\"1.3.3\"  -fPIC -o extensions/libipt_string_sh.o -c extensions/libipt_string.c
extensions/libipt_string.c: In function `parse_string':
extensions/libipt_string.c:50: error: `BM_MAX_NLEN' undeclared (first use in this function)
extensions/libipt_string.c:50: error: (Each undeclared identifier is reported only once
extensions/libipt_string.c:50: error: for each function it appears in.)
extensions/libipt_string.c:50: error: structure has no member named `string'
extensions/libipt_string.c: In function `parse_hex_string':
extensions/libipt_string.c:95: error: structure has no member named `string'
extensions/libipt_string.c:117: error: structure has no member named `string'
extensions/libipt_string.c:123: error: structure has no member named `string'
extensions/libipt_string.c:126: error: `BM_MAX_NLEN' undeclared (first use in this function)
extensions/libipt_string.c:130: error: structure has no member named `len'
extensions/libipt_string.c: In function `parse':
extensions/libipt_string.c:154: error: structure has no member named `len'
extensions/libipt_string.c:154: error: structure has no member named `string'
extensions/libipt_string.c: In function `print':
extensions/libipt_string.c:240: error: structure has no member named `string'
extensions/libipt_string.c:240: error: structure has no member named `len'
extensions/libipt_string.c:242: error: structure has no member named `string'
extensions/libipt_string.c:242: error: structure has no member named `len'
extensions/libipt_string.c:245: error: structure has no member named `string'
extensions/libipt_string.c:245: error: structure has no member named `len'
extensions/libipt_string.c: In function `save':
extensions/libipt_string.c:257: error: structure has no member named `string'
extensions/libipt_string.c:257: error: structure has no member named `len'
extensions/libipt_string.c:259: error: structure has no member named `string'
extensions/libipt_string.c:259: error: structure has no member named `len'
extensions/libipt_string.c:262: error: structure has no member named `string'
extensions/libipt_string.c:262: error: structure has no member named `len'
make[3]: *** [extensions/libipt_string_sh.o] Error 1
make[3]: Leaving directory `/openwrt/whiterussian/openwrt/build_mipsel/iptables-1.3.3'
make[2]: *** [/openwrt/whiterussian/openwrt/build_mipsel/iptables-1.3.3/.built] Error 2
make[2]: Leaving directory `/openwrt/whiterussian/openwrt/package/iptables'
make[1]: *** [iptables-compile] Error 2
make[1]: Leaving directory `/openwrt/whiterussian/openwrt/package'
make: *** [package/compile] Error 2

I have found out that the compile problem might go away by using iptables-1.3.3-20051023 as is told over here.
Unfortunately, the patching files of the openwrt build do not accept this other version (the differences are really big), so this is not a real solution.
I am looking for a version of the file ipt_string.h that will cooperate with the openwrt version of libipt_string.c,

So far, I am stuck. Any help would be appreciated.

Thanks! On Debian, the correct incantation was "apt-get install zlib1g-dev".

I did not run into the problem you describe, but I'm using Debian instead of FC5. Actually, I'm running Debian inside VMware on top of FC5, because I'm a longtime RedHat user but they say that Debian is the preferred development platform for OpenWrt. VMware Server is free (gratis) and you only need about 3 gigs of disk space to install Debian inside VMware.