Perl procura por módulos nos diretórios da matriz @INC , assim como o Bash faz com $PATH para comandos. O GD instalado pelo apt provavelmente está sendo substituído por outra coisa no @INC .
Procure arquivos com o nome GD.pm em seu sistema, ele deve mostrar apenas o do Debian em /usr/lib/perl5/GD.pm .
Você pode verificar seu @INC usando perl -e 'print join "\n", @INC' , o meu é
/etc/perl
/usr/local/lib/perl/5.10.1
/usr/local/share/perl/5.10.1
/usr/lib/perl5
/usr/share/perl5
/usr/lib/perl/5.10
/usr/share/perl/5.10
/usr/local/lib/site_perl