check to see if you have an rpm installed version of libgd (redhat and many other distros install libgd by default).
Do an 'rpm -qa|grep gd' to see if your machine already has libgd installed in the default directory. If that's the case, then php is probably configuring against the .so version when you leave out the path in the --with-libgd switch.
Check your other packages too, like apache, or mysql, for two installs, because mixing library versions can happen if you get things set up just right (just wrong??? :) with two versions of the same app floating around.
rpm -e the old rpms to get rid of them.