Could not establish trust connection when accessing webservices within .NET Framework with certificate

I'm trying to call a webservice (not mine), Service-Referencing it within Visual Studio 2008. According to it's owner, it requires a certificate, which they kindly provided for testing purposes.

I'm an absolute newbie in certificates, SSL and else, so I could be doing something terribly wrong here. Anyways, this is what I did.

First, I registered the P12 file along with it's password (also provided) in my client machine. Then, I referenced the service using the Service Reference option in VS2008, and pointed to their URL (which, btw, uses a VPN tunnel) for it to be called within a windows form application. All of their underlying methods are recognized by the generated assemblies.

Here's the code I used:

WebServiceClient client = new WebServiceClient();
X509Store store = new X509Store(StoreName.My, StoreLocation.CurrentUser);

store.Open(OpenFlags.ReadOnly);
X509Certificate2 certificate = store.Certificates[0]; 
client.ClientCredentials.ClientCertificate.Certificate = certificate;

client.ReturnSomeData(); //Error here

At the last line, the following exception is thrown:

Could not establish trust relationship for the SSL/TLS secure channel with authority '<webservice URI here>'

The inner exceptions are the same 2 levels deep, and the third one is

The remote certificate is invalid according to the validation procedure

Problem is, I can call that very method using that very certificate at SoapUI, and data is returned.

Also, I've seen the Troubleshooting Marc Gravel posted here , so ...

Do you have DNS and line-of-sight to the server? Yes
Are you using the correct name from the certificate? Yes, I checked it with Immediate.
Is the certificate still valid? Hopefully. If SoapUI accepted it, I guess it is? (Really have my doubts here)
Is a badly configured load balancer messing things up? Also doesn't explain SoapUI's behaviour.
Does the new server machine have the clock set correctly (i.e. so that the UTC time is correct [ignore local time, it is largely irrelevent]) - this certainly matters for WCF, so may impact regular SOAP? Dunno if appliable.
Is there a certificate trust chain issue? if you browse from the server to the soap service, can you get SSL? Actually, there is. Chrome reports that The website's identity could not be confirmed. I assumed it would be due to eh fact that we're using a VPN connection here. Is there a problem?
Is the server's machine-level proxy set correctly? (which different to the user's proxy); see proxycfg for XP / 2003 (not sure about Vista etc) Again, won't explain SoapUI's behaviour.

Any help deeply appreciated.

Solution

I managed to receive the certificate directly importing it from the .p12 file. The following code

X509Certificate2 certificate = new X509Certificate2();
certificate.Import(@"<FilePath>",password,X509KeyStorageFlags.DefaultKeySet);
client.ClientCredentials.ClientCertificate.Certificate = certificate;

client.ReturnSomeData();

is successfull, so I'm sticking with this solution for now. It's not ideal, but seeing how urgent this matter is, I'm changing it later on.

Still not a definitive answer, though this might help whomever has a similar problem.

UPDATE

I think I figured out why this answers the question. So, as it turns out, something is still wrong with the way I retrieve the certificate from the store. Directly importing it ensures that the certificate is there, but a few extra steps were needed for the client to connect.

First, defining the transport mode in the binding.

<binding name="<bindingName>">
        <security mode="Transport" >
            <transport clientCredentialType="Certificate" />
        </security>
</binding>

Secondly, ensuring that the ServerCertificateValidationCallBack callback is doing the right validation. As bad as it seems,

ServicePointManager.ServerCertificateValidationCallback += 
    (sender, x509Certificate, chain, errors) => true;

will work FOR NON-PRODUCTION PURPOSES.