I was recently having the same problem. I found one explanation here that worked for me. Specifically, the permissions for the private key. The full info is copied below.

There are a couple things that I would look at first:

1. Do you have a private key for this certificate?
2. Have you given permission for youf application to access the private key?

You can establish whether you have a private key by viewing the certificate through the Windows Certificate Store. To get to this, follow these steps:

1. From the Windows Start menu, select Run.
2. Type mmc in the Open: field. Click OK
3. Select "Add/Remove Snap-in" from the File menu.
4. Click the Add button.
5. Select "Certificates" from the list of Available Standalone Snap-ins. Click the Add button.
6. Select "Computer account." Click Next.
7. Select "Local Computer". Click Finish.
8. Click Close.
9. Click OK.
   10. Expand the Certificates node under the Console Root and open the Personal store.
   11. Double-click the Certificate you re using. If you have a private key, the dialog will display a message at the bottom that says "You have a private key that corresponds to this certificate".

If you have a private key, then ensure that your application has permission to access the key:

1. Open Windows Explorer.
2. Navigate to the C:Documents and SettingsAll UsersApplication DataMicrosoftCryptoRSAMachineKeys folder.
3. Select the files containing the keys that the WSE will need to retrieve.
4. From the File menu, select Properties.
5. On the Security tab, add the ASPNET account and select th e Full Control option.
6. Notes: 1. Determining which key file in the MachineKeys folder is associated with a certificate can be difficult. One easy method is to note the creation date and time when creating a new certificate. When you view the files in the MachineKeys directory, check the Date Modified field for the corresponding date and time. 2. If you have configured your system to run under a different account than ASPNET, use that account when granting permissions to access the certificate.

As per my experience it could be failing because of two reasons.

1. Check if your cert has private key available.
2. If that is .net application then check if you have given permission to cert to make sure your application has permission to access the cert. In my case adding the "iis_iusrs" and given read permission does work for me. Thanks.

After encountering the same exception: System.Security.Cryptography.CryptographicException, Object contains only the public half of a key pair, I proofed an alternative, but less optimal solution.

Situation: Certificate / key look up worked great inside of Visual Studio IIS Express, but while the Web Application was running under the proper IIS service, I always received the Contains only public half of key pair exception.

I used the WSE3 CertificateTool to locate the private key section on the filesystem and attempted at length to adjust the user permission settings to give the ASP user permissions as per the above answer.

My eventual fix, which was not pretty, was to create a new IIS Application Pool specific to my Web service code and set the user Identity the pool runs as the Local machine owner of the certificate + private key.

The final location I installed the certificate in was "Local Computer / Trusted People".

Using WSE3 CustomPolicyAssertion, C# .NET:

clientToken = X509TokenProvider.CreateToken(StoreLocation.LocalMachine, 
   StoreName.TrustedPeople, "soap.partnersite.com", X509FindType.FindBySubjectName);

After updating the App Pool Identity, no private key file overrides were necessary when changing the application pool owner.