I had a similar problem last year. After trying several things I gave up on doing WSDL in Perl and wrote my project in Java.

Since then XML::Compile has come on the scene. I have heard better things about its WSDL support than previously Perl modules, but I have not personally tried it. Still it is worth a shot.