Turns out the issue was an old zlib-devel package. For reference, the latest version was not included in the standard RHEL5 install. When running Bugzilla's checksetup.pl, it suggested this could be the issue. After doing a fresh install, it installed fine.

Thanks for the assistance.

Also, for reference, YUM is Redhat's package manager (like Debian's apt-get).