Yes if a distro is rolled on unix so no problem on windows, but not vice versa, apparently. I was greatly confused because if one makes a pure-perl module without magic or compilers involved, one can reasonably expect that windows distro-rolling is very smooth. And this problem was very basic, that's why my confusion.

Anyway you might want to add to your tutorial how to package bin/ scripts, either use #!perl or nothing at all, but not #!something-else or be prepared to be bitten.