Can anyone point me in the direction of how to debug this? Trace this? Kill this with fire?

Caveat: I have no experience with Apache::Soap but a quick observation I can give.

This:

PerlSetVar dispatch_to "/usr/local/lib/perl5/5.12.4, /usr/local/lib/
+perl5/site_perl/5.12.4, /usr/local/***company_name****/current/perl_l
+ib"
[download]

doesn't seem to fit this pattern:

PerlSetVar dispatch_to "/Your/Path/To/Deployed/Modules, Module::Name, 
+Module::method"
[download]

I'd also be looking at what the PATH variable is set to and make sure it includes the path to where the modules it is complaining about live and there is more than one place to look.