What is the first line of the script (shebang)? It's likely that the perl executable in your path is different from the system's default - and only the one in the path has all necessary modules installed.

I've been using #!/usr/bin/env perl as the first line for a while now - and never regretted doing so. EDIT: Sorry, this only applies to *nix-like systems and the question was about Windows.

P.S. What OS are you using, BTW?