I have encountered this kind of problems before. Have a look at the namespaces in your wsdl and make sure that there are correct. Make sure types are fully qualified.
Thanks for the tip, Leslie. Turned out the problem was that the wsdl was, in fact, wrong. It was autogenerated with java2wsdl, and failed to define types for secondary interface references. I've posted to axis-dev about this problem, but in the meantime using concrete types throughout my service's dependancy hierachy seems to work (but is a major pain).
