iainspeed:
I've been trying to build zlib (any version) onto a Debian 5.1 machine, and had a few problems. I've solved these now, but one of them was a dependence on not only zlibc/zlib1g as you'd expect, but zlib1g-dev as well, and wasn't actually in any of the error messages. I ended up relying on a solution given for a similar problem with mySQL installation.
I noticed that Hackage only lists Haskell library dependencies - might it be an idea to list other non-Haskell ones, too? cabal-install won't install without zlib, so there's no ease of installation to rely on, and not everyone would have found/read the mySQL post.
The cabal file lists zlib as a dependency: extra-libraries: z however, what 'z' means varies from distro to distro. Ultimately, your package manager has to solve this. -- Don