I can't get it to work with Makefile.PL either. I get pretty much the same errors. If I use the Build.PL, though, it seems to work:

$ perl ./Build.PL
Checking whether your kit is complete...
Looks good

Checking prerequisites...
Looks good

Deleting Build
Removed previous script 'Build'

Creating new 'Build' script for 'Contextual-Return' version 'v0.1.0'
$ ./Build test
lib/Contextual/Return.pm -> blib/lib/Contextual/Return.pm
lib/Contextual/Return/Failure.pm -> blib/lib/Contextual/Return/Failure
+.pm
t/00.load...........ok 1/1# Testing Contextual::Return v0.1.0
t/00.load...........ok
t/SCALAR............ok
t/args..............ok
t/context_tests.....ok
t/fail..............ok
t/fail_with.........ok
t/failures..........ok
t/fixed.............ok
t/interp............ok
t/lazy..............ok
t/lvalue............ok
t/nonvoid...........ok
t/object............ok
t/pod-coverage......ok
t/pod...............ok
t/scalar-to-list....ok
t/simple............ok
All tests successful.
Files=17, Tests=184,  3 wallclock secs ( 1.54 cusr +  0.29 csys =  1.8
+3 CPU)
[download]

Perhaps using the Module::Build alternative will work for you. If so, please file a bug report on the ExtUtils::MakeMaker install process at http://rt.cpan.org/Public/Dist/Display.html?Name=Contextual-Return