Just reading through the Makefile.PL, I find it a little hard to follow with any certainty. It looks to me that it should be working ok for you - but perhaps there's a bug in the checks that it performs. What happens if you replace the existing Makefile.PL with this:

use ExtUtils::MakeMaker;

WriteMakefile(
    'NAME'    => 'XML::LibXSLT',
    'VERSION_FROM' => 'LibXSLT.pm', # finds $VERSION
    'AUTHOR'    => 'Matt Sergeant',
    'ABSTRACT'  => 'Interface to Gnome libxslt library',
    'PREREQ_PM' => { 'XML::LibXML' => "1.58", },
    'LIBS'      => ['-lxslt -lxml2 -lz -lm'],
    'OBJECT'     => '$(O_FILES)',
);
[download]

Even if you get some warnings when running that Makefile.PL, follow it up by running 'make' and see what happens. If it doesn't work you can always start over again by first running 'make clean'.

Cheers,
Rob