I'll give this a try ... there are several potential reasons for this behavior.
A) If you're client test tool is built within IE and your SSL cert is self-signed, you'll always have problems with IE not accepting the certificate, and adding the cert to your client's "trusted" group won't help. IE hates self-signed certs and going through MS's Import routine is a waste of time.
B) If your client test tool is a self-built application, you shouldn't need to add the certificate to the trusted group even if it's self-signed. But you might need to add this to your code (for testing) in order to avoid the self-signed certificate glitch:
System.Net.ServicePointManager.CertificatePolicy = New TrustAllCertificatePolicy()
C) Assuming you're using a self-signed certificate, be careful how you create the certificate. This was a problem for me until I came up with these commands:
rem creates root authority file and cert in currentuser\root and gives it the right to sign certs
makecert.exe -a sha1 -n CN=CAS_Temp_Authority %Host_Authority_Cert_Name% -sr LocalMachine -ss Root -sky signature -pe -r -sk MyNewKey -cy authority
rem creates ssl cert, puts it in the currentuser\root authority and signs it based on the other certificate
makecert.exe -n cn=%Host_URL% %Host_Cert_Name% -is root -ic %Host_Authority_Cert_Name% -sky exchange -pe -sv %Host_Cert_PrivateKey% -eku 1.3.6.1.5.5.7.3.1
rem make the pfx file that will allow you to copy certs around with private keys
pvk2pfx -pvk %Host_Cert_PrivateKey% -spc %Host_Cert_Name% -pfx %Host_Cert_PFX% -f
As you can imagine, the "authority" cert (*.cer file) generated from that goes into your "trusted root..." store, the other exchange cert goes into your Local Machine / My store, but you want to import it as the *.pfx file, not the *.cer file. At least that worked for me.
Lastly, if A) and B) don't help you might try changing your SecurityMode from TransportWithMessageCredential to regular Transport and see if that makes a difference.
Good luck. Sorting out these WCF/SSL issues is tough for everyone.