You could try using the latest gcc, GCC 3.1. RedHat has been known to ship some seriously strange and/or "controversial" compilers, and 2.96 is one of those. If you can, try and upgrade.
Otherwise, this could be a simple case of library linkage problems. A good whack with ldconfig might help.