If you can't just perl Makefile.PL && make && make test && make install then you have a broken Perl install. There are all sorts of options from an edit and recompile, rpm install or perhaps an ActiveState release that will solve the problem. As noted Digest::MD5 is the actual workhorse, with MD5 just a thin deprecated wrapper over it. I would suggest simplifying. First don't use CPAN. Download the tarball and do a tar -xzf Digest-MD5.tar.gz; cd Digest-MD5 and then try the usualy perl Makefile.PL. Have you tried this?

[root@devel3 root]# cd /usr/src


[root@devel3 src]# wget http://www.cpan.org/authors/id/G/GA/GAAS/Diges
+t-MD5-2.30.tar.gz


--10:18:51--  http://www.cpan.org/authors/id/G/GA/GAAS/Digest-MD5-2.30
+.tar.gz
           => `Digest-MD5-2.30.tar.gz'
Resolving www.cpan.org... done.
Connecting to www.cpan.org[63.251.223.172]:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 43,746 [application/x-tar]

100%[====================================>] 43,746       296.67K/s    
+ETA 00:00

10:18:55 (296.67 KB/s) - `Digest-MD5-2.30.tar.gz' saved [43746/43746]


[root@devel3 src]# tar -xzf Digest-MD5-2.30.tar.gz 


[root@devel3 src]# cd Digest-MD5-2.30


[root@devel3 Digest-MD5-2.30]# perl Makefile.PL


Testing alignment requirements for U32... no restrictions
Checking if your kit is complete...
Looks good
Writing Makefile for Digest::MD5
[root@devel3 Digest-MD5-2.30]# make
cp MD5.pm blib/lib/Digest/MD5.pm
/usr/bin/perl -I/usr/lib/perl5/5.6.1/i386-linux -I/usr/lib/perl5/5.6.1
+ /usr/lib/perl5/5.6.1/ExtUtils/xsubpp  -typemap /usr/lib/perl5/5.6.1/
+ExtUtils/typemap -typemap typemap MD5.xs > MD5.xsc && mv MD5.xsc MD5.
+c
gcc -c  -fno-strict-aliasing -I/usr/local/include -O2 -march=i386 -mcp
+u=i686   -DVERSION=\"2.30\" -DXS_VERSION=\"2.30\" -fPIC -I/usr/lib/pe
+rl5/5.6.1/i386-linux/CORE  MD5.c
Running Mkbootstrap for Digest::MD5 ()
chmod 644 MD5.bs
rm -f blib/arch/auto/Digest/MD5/MD5.so
LD_RUN_PATH="" gcc  -shared -L/usr/local/lib MD5.o  -o blib/arch/auto/
+Digest/MD5/MD5.so     
chmod 755 blib/arch/auto/Digest/MD5/MD5.so
cp MD5.bs blib/arch/auto/Digest/MD5/MD5.bs
chmod 644 blib/arch/auto/Digest/MD5/MD5.bs
Manifying blib/man3/Digest::MD5.3pm


[root@devel3 Digest-MD5-2.30]# make test


PERL_DL_NONLAZY=1 /usr/bin/perl -Iblib/arch -Iblib/lib -I/usr/lib/perl
+5/5.6.1/i386-linux -I/usr/lib/perl5/5.6.1 -e 'use Test::Harness qw(&r
+untests $verbose); $verbose=0; runtests @ARGV;' t/*.t
t/align......ok                                                       
+       
t/badfile....ok                                                       
+       
t/clone......ok                                                       
+       
t/files......ok                                                       
+       
t/md5-aaa....ok                                                       
+       
t/utf8.......ok                                                       
+       
All tests successful.
Files=6, Tests=273,  5 wallclock secs ( 0.32 cusr +  0.02 csys =  0.34
+ CPU)


[root@devel3 Digest-MD5-2.30]# make install


Installing /usr/lib/perl5/site_perl/5.6.1/i386-linux/auto/Digest/MD5/M
+D5.so
Files found in blib/arch: installing files in blib/lib into architectu
+re dependent library tree
Installing /usr/lib/perl5/site_perl/5.6.1/i386-linux/Digest/MD5.pm
Installing /usr/share/man/man3/Digest::MD5.3pm
Writing /usr/lib/perl5/site_perl/5.6.1/i386-linux/auto/Digest/MD5/.pac
+klist
Appending installation info to /usr/lib/perl5/5.6.1/i386-linux/perlloc
+al.pod


[root@devel3 Digest-MD5-2.30]#
[download]

You might also try adding --PREFIX=/path/for/install and or --LIB= to the perl Makefile.PL line.