The "Tester" complexType looks very simple. I have much more complicated classes which work fine.

SOAP::WSDL doesn't have any trouble producing compliant messages for that WSDL. The web-service must be rejecting messages that are valid for the WSDL you've pasted. It'd be very useful to get some idea of what the web-service (or WCF deserialiser) thinks is wrong with the message... alas I have no idea how to do that.

Are you still getting warnings about unsupported schema/import features? (and you're on SOAP::WSDL 1.23 correct?)

-David