You seem to be having the same troubles I was. I didn't have permissions to the Perl library directory, which is where - when I did a 'make install' - the module was attempting to install itself.

Here's your solution I belive: You said that INSTALLPRIVLIB, INSTALLARCHLIB, INSTALLSITELIB, INSTALLSITEARCH, INSTALLBIN, and INSTALLSCRIPT where all set incorrectly. To correct that, just do what you did with PREFIX. Any of those variables can be overridden. As in:

perl Makefile.PL INSTALLPRIVLIB=/my/dir INSTALLARCHLIB=/my/dir etc.

That's worked for me.