If you used cpan or cpanm to try to install the module, one of the first steps you could do is inspect the log files in your ~/.cpan or ~/.cpanm directory. If you don't have SSH / console access - but have FTP access - it may be possible to use the App::Cpanminus module to install the relevant modules - invoking it from a script in your cgi-bin directory (as the job description implies you might have considered doing already).
If you are not willing to share your login details, I can send instructions / script by e-mail - it might just take fractionally longer that way.
My experience: approximately 12 years of using Perl on and off - in a variety of environments (CGI, Plack/PSGI mostly); and small-scale VPS administration for approximately 10 years.