1) It's legal to distribute modules that are GPL and/or Artistic, as long as you abide by their licenses. You should check the license of each module.
2) Your Modules namespace is causing problems. While 'use Modules::LWP::Simple' may work without an error, the loaded module undoubtedly identifies a different package:
package LWP::Simple;
That may be causing your problem with XML::Simple, though I haven't tried it to see.
It would be better to instruct the user to drop the extra modules in a directory of their choice and modify the 'use lib' line at the top of your script to refer to it. Besides, the user may be just fine with CPAN and already have the modules installed.
