I struggled with this problem for quite a while until I finally figured it out. The problem in my case, and I think this is true for many people, is that I had the RedHat (6.2) gd-devel package installed, as well as the 1.8.3 gd library that I compiled. Even though I specified --with-gd=/usr/local, which points to the one I compiled, the configure script queried the RedHat library and therefore thought that it had gdImageCreateFromGif (and didn't have the Png and Jpeg variants, which are in the lib I compiled). But in the make cycle, the one I compiled is used and, behold, gdImageCreateFromGif was missing.
The solution was simply to remove the RedHat gd development package (rpm -e gd-devel). This left only the libgd.a that I compiled, and configure correctly determined the available gd functions.
I hope this helps. I read a ton of posts and really thrashed on this until I figured it out.
