To begin with, you are right, how the WSDL is formed and what it contains has nothing to do with any SSL layer concern. The WSDL just described what methods the web service exposes and what parameters they accept and how the requests/results should be encoded in XML. It also specifies the endpoint address the web service could be found running at.
Thus, from what you tell us, I can only imagine one thing happening: The remote party probably has a piece of code that actually checks the SSL certificate parameters to ensure the safety of the communication. It is not very common but some clients do like to check that the fingerprint of the SSL certificate of the remote party matches a known fingerprint so that they can feel safe that their system will fail if some has found a very clever way of masquerading as your SSL secured site. If this is the case, I am afraid there is not much you can do on your end to rectify the situation. I can only advise that you ask the remote party to check to see if they have any checks for the SSL certificate fingerprint/details in their code/software. After all, the change of an SSL certificate should not be breaking an application which runs on top of that secure connection.