And can you find GD.pm in the mentioned @INC paths? If I'm guessing correctly, you are using some kind of Debian system; on this system the file should be placed in /usr/lib/perl5/GD.pm.

If, however, you installed GD with CPAN, look inside /usr/local/lib/perl/5.10.0 (or /usr/local/share/perl/5.10.0 by accident).