You are not the first person that has had this problem, including myself. What always works, is to get the latest GD c lib from boutell.com and compile it yourself, after reading the docs on how to include png and gif support. Then make sure you get no errors, and don't have 2 gd libs installed with 2 different header files. You may have headers and libs in /usr /usr/local and /usr/X11R6. These will conflict, so make sure you have only one. The same is true for libpng and libgif and/or libungif. Make sure you have only one, and only it's matching header file in the various include directories. Then once you have libgd properly installed, install the Perl GD module, and watch for errors.
The reason this all comes about, is usually your "linux distribution" puts these in different places, depending on how they like to do things. BUT when you get source tarballs, they will usually default to putting things in /usr/local, without checking for other versions....so you can end up with dual libraries, and multiple header files. Then depending on how your search paths are setup, you may get 1 header file assigned to a wrong library version, or some other glitch.
Also, I can't say for sure whether you using Perl version 5.61 is causing some problem. The GD people always go with the "current releases" and seem to care little about insuring backward compatibility. You can read the Changelog for the module to see what libgd version it requires.
Also from vague memory, their was some changes in libpng awhile ago, so maybe you need to reinstall the latest libpng first, BEFORE building libgd. There are alot of details to getting GD installed properly. You can groups.google search for "GD png" and maybe get some tips.
Also, if you are stuck using Perl561, maybe ask around for people who still have this version, and what level libgd they use, and which older Perl GD module is compatible with it.
I'm not really a human, but I play one on earth. flash japh