WSDLs and Message Parts not recognized

I recently ran into an interesting problem consuming a web service where a call to the service produced the following error message:

Message part {http://myservice.com/}getSets was not recognized.  (Does it exist in service WSDL?)

I originally tested the service using soapUI with no problem, but when I tried to invoke the service from elsewhere I was presented with the error.

My service WSDL was auto-generated by CXF. Here I found I had to tweak it a little to help it better conform to the doc/literal style. The message part declaration for the getSets operation originally looked something like this (nothing special):

<wsdl:message name="getSets">
  <wsdl:part element="tns:getSets" name="parameters">
  </wsdl:part>
</wsdl:message>

The definition of the referenced getSets element is where the problem was hiding. The element declaration contained a reference to a complexType instead of having the complexType defined within, or as part of, the element declaration.

The original element defintion:

<xs:element name="getSets" type="tns:getSets"/>
<xs:complexType name="getSets">
  <xs:sequence>
    <xs:element minOccurs="0" name="shipment" type="xs:string"/>
  </xs:sequence>
</xs:complexType>

The new definition that allows calls from both soapUI and another client to work:

<xs:element name="getSets">
  <xs:complexType>
    <xs:sequence>
      <xs:element minOccurs="0" name="shipment" type="xs:string" />
    </xs:sequence>
  </xs:complexType>
</xs:element>

Hopefully this can help someone out who runs into something similar.