ok bro... a little late in the making, but as promised, here's what I had to do to install your module successfully on a pristine Ubuntu 11.10 machine:
1 mkdir devel
2 cd devel
3 wget http://search.cpan.org/CPAN/authors/id/R/RF/RFREIMUTH/Rand
4 tar -xzvf RandomJungle-0.04.tar.gz
5 cd RandomJungle-0.04/
6 perl Makefile.PL
8 make test
*** expected errors due to deps
9 sudo perl -MCPAN -e 'install Test::Warn'
10 make test
*** more expected errors
12 sudo perl -MCPAN -e 'install Devel::StackTrace'
13 make test
*** again, expected errors
14 sudo perl -MCPAN -e 'install DBM::Deep'
15 sudo perl -MCPAN -e 'install XML::Twig'
16 sudo perl -MCPAN -e 'force install XML::Twig'
*** force didn't work, so I did some research, but not before
manually testing things on my own...
17 cd ..
18 wget http://search.cpan.org/CPAN/authors/id/T/TO/TODDR/XML-Pars
19 tar -xzvf XML-Parser-2.41.tar.gz
20 cd XML-Parser-2.41/
*** with another failure here, I resorted to good ol' google.
Ironically, it was this PerlMonks post that sent me in the right direction, then I continued...
26 sudo apt-get install libexpat1-dev
28 sudo perl -MCPAN -e 'install XML::Twig'
*** success with XML::Twig!!
29 cd ..
30 cd RandomJungle-0.04/
31 make test
33* sudo make install
*** and all is good :)
From what I can tell, you have all your bases covered :)