If that's how it's done, I think this happens: Your program has been built as a perl interpreter which has the compiled bytecode of your perl program included.
Note that this will include all the supplied Perl modules, too. Unfortunately Perl2Exe is actually a perl5.6.0, while you have an ActiveState perl5.6.1.

Thus your library pathes are different...
I'd try if that error still occurs when removing the ActiveState perl or running perl2exe on your program on a computer which has never seen any perl installation

If any of this fails, I suggest you try to get a hold of an old ActiveState perl5.6.0
an try again.

Who is the vendor of perl2exe? (I remotely remember fooling around with that...but it's not coming to me right now...:-)).
The vendor should have a perl5.6.1 version of perl2exe IMHO.
Otherwise I would count it as a discontinued product and refrain from using it.

IMHO everyone's served better if you bundle a perl installation with all required modules/libraries/custom programs and just installed that at your clients' location.

Kay