> That's one of the first things that came to mind, so I specifically
> checked that both "zlib" and "zlib-dev"(or whatever it's called) are
> installed.  Makes no difference.

Have you tried uninstalling and reinstalling ruby and its related packages 
after making sure zlib and zlib-dev are installed?