I have never used h2xs, but I suspect there is something wrong with how it is installed on your system. On my Unix system I tried:

> head `which h2xs`
#!/cad/apps/gnu/solaris/bin/perl
    eval 'exec /cad/apps/gnu/solaris/bin/perl -S $0 ${1+"$@"}'
    if $running_under_some_shell;

=head1 NAME

h2xs - convert .h C header files to Perl extensions

=head1 SYNOPSIS

> which perl
/cad/apps/gnu/solaris/bin/perl
[download]

So, on my system, the full path to the perl executable matches that inside the h2xs script. You could try this.