After a bit of mucking about, I found this post on the internet.
Turns out that the WSDL provided had a snippet like:
<wsdl:message name="someMessageRequest">
<wsdl:part name="parameters" element="ns0:someMessageRequest"/>
</wsdl:message>
<wsdl:message name="someMessageResponse">
<wsdl:part name="parameters" element="ns0:someMessageResponse"/>
</wsdl:message>
... SNIP ...
<soap:operation style="document" soapAction="someMessage"/>
<wsdl:input>
<soap:body use="literal" parts="parameters"/>
</wsdl:input>
<wsdl:output>
<soap:body use="literal" parts="parameters"/>
</wsdl:output>
Because it uses the same name for both request and response parameters, wsdl.exe is unable to resolve it and dies.
My fix:
<wsdl:message name="someMessageRequest">
<wsdl:part name="parametersRequest" element="ns0:someMessageRequest"/>
</wsdl:message>
<wsdl:message name="someMessageResponse">
<wsdl:part name="parametersResponse" element="ns0:someMessageResponse"/>
</wsdl:message>
... SNIP ...
<soap:operation style="document" soapAction="someMessage"/>
<wsdl:input>
<soap:body use="literal" parts="parametersRequest"/>
</wsdl:input>
<wsdl:output>
<soap:body use="literal" parts="parametersResponse"/>
</wsdl:output>
Now the proxy is generated.
Part of the fun of SoA is that you can never trust the WSDL's you are provided to work :)