I'll update here if I figure this out.
Turns out that I have both libgif 4.1.6 and libgif 5.1.0 on my system.
In some juggling of LD_LIBRARY_PATH and INCLUDE_PATH, the gif_lib.h of v5.1.0 got read, but the libgif.so of v4.1.6 got used (even though the newer v5.1.0 libgif.so was in the LD_LIBRARY_PATH too).
To fix this, I moved the "-L/path/containing/
5.1.0.so" *before* the "-L/path/containing/
4.1.6.so" and this issue got fixed.
After this builds fine properly, I will move libgif/libungif 4.1.6 completely out of LD_LIBRARY_PATH and INCLUDE_PATH (not sure why libungif doesn't exist for 5.1.0).