SSL certificates: no client certificate key.

I am trying to access a WCF web service that uses two-way SSL encryption. When I try to call the service, I get

System.ServiceModel.Security.SecurityNegotiationException: Failed to establish a secure channel for SSL / TLS with authority "XXX.xx". ---> System.Net.WebException: The request was aborted: Failed to create SSL / TLS secure channel.

I tried activating the wired shark to see what is being sent to and from the server: I see the client's greeting and the server's greeting. But there is no client response to the server. I expected

"Client Key Exchange Certificate. Replace Cipher. Encrypted Handshake Message"

but nobody is sent. I think it is a problem with the certificate sent by the server, that somehow my client server is not managing it.

Here's what I've already tried: I generated a certificate through the appropriate authority, although I might have made a mistake requesting a certificate without knowing it. I added two root certificates: Trusted Root Certificates, Trusted Publishers and Trusted Individuals. I also added client certificate to trusted people. A colleague of mine succeeded in establishing a connection on a win 2008 server (I am using 2003 because it is needed for some odd reason - don't ask). I don't see any difference in our approach, so I'm a bit lost.

Any help would be greatly appreciated.