Vamos começar do começo: existe algum motivo em especial pelo qual você está usando o HttpClient para consumir o serviço? Digo isso porque existem bibliotecas, como o Apache CXF, que fazem isso de maneira totalmente transparente, sem grandes problemas.
Aliás, o web service em questão é WS-* ou REST? A solução é diferente, dependendo do tipo.
Nós já fazemos algo parecido com isso. Na verdade parece que este certificado ai SSL_RSA_WITH_DES_CBC_SHA é fraco. Parece que a questão é descobrir como o HttpClient possa aceitá-lo, já que ele é fraco. Mas não achei como