I'm having the same problem, but when I run:

ruby extconf.rb

I get:

# ruby extconf.rb
checking for deflateReset() in -lz... no
checking for deflateReset() in -llibz... no
checking for deflateReset() in -lzlib... no

What a brick wall. =/

- Rabbit