Please post the exact versions of perl, PAR, and PAR::Packer you're using as well as how and from where you installed them. That may help us figure out what's going wrong. If you installed PAR/PAR::Packer via PPM, try installing it from the bribes.org repository instead of the ActiveState one.
Furthermore, you could unzip the generated executable (you should be able to open it like a zip file) and see what's in there. Are the files that are reported missing actually in the file?