In 'the old days' (before Mendix could deal with choice elements) I used to change 'em into sequence instead. Might or might not help in your specific case, but you can give it a shot.
Bert,
Without more detail it is not completely clear what is happening, but from this blog post I would assume that the changes will be necessary. Changing the wsdl will not help in this case, I think. Can you maybe edit your question with the choice elements from the wsdl? Then a more detailled answer can possibly be provided.