Going by ldd output and configure.ac, giflib[X] or more exactly gif2x11 needs only libX11, not the other three libs (libXt,libICE,libSM). The other come up in the log only due to use of AC_PATH_XTRA.
...unfortunately, to fully fix it, X_PRE_LIBS will need to be removed from configure.ac, otherwise we'd end up with automagic.
*** Bug 517292 has been marked as a duplicate of this bug. ***
this became a build time failure with the new giflib-4.1.6-r3 as the extra deps were incorrectly deleted from the ebuild should be fixed in the tree now though: http://sources.gentoo.org/media-libs/giflib/giflib-4.1.6-r3.ebuild?r1=1.8&r2=1.9
looks like giflib-4.2.3-r1 was also broken http://sources.gentoo.org/media-libs/giflib/giflib-4.2.3-r1.ebuild?r1=1.4&r2=1.5