Try the following short C program:

#include <unistd.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>

int main(int argc, char** argv){
    execl("sadlfjsdf", "foo");
    printf("%s\n", strerror(errno));
}
[download]

If that says No such file or directory it's most likely a perl problem, and you should contact p5p. If it says Not a directory, it's most likely a Fedora problem (and I guess you should contact the Fedora developers).

BTW do you have a single dot in your $PATH? (Don't know if that makes a difference)