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
+omJungle-0.04.tar.gz
    4  tar -xzvf RandomJungle-0.04.tar.gz 
    5  cd RandomJungle-0.04/
    6  perl Makefile.PL 
    7  make
    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'

    *** doa

   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
+er-2.41.tar.gz
   19  tar -xzvf XML-Parser-2.41.tar.gz 
   20  cd XML-Parser-2.41/
   23  make
   
    *** with another failure here, I resorted to good ol' google.
[download]

Ironically, it was this PerlMonks post that sent me in the right direction, then I continued...

   26  sudo apt-get install libexpat1-dev
   27  make
   28  sudo perl -MCPAN -e 'install XML::Twig'

    *** success with XML::Twig!!

   29  cd ..
   30  cd RandomJungle-0.04/
   31  make test
   32* 
   33* sudo make install

    *** and all is good :)
[download]

From what I can tell, you have all your bases covered :)