I've had the worst time with Fedora, in that it's often missing header files. In the case of GD, it's missing the gd.h and other header files. Sigh.
What I've resorted to in the past is to download the GD source for the GD version I have (rpm -qa | grep gd) and then manually install gd.h into /usr/include or wherever.
