Non conosco questi WCF Service ma conosco i certificati, sarà un X.509. Il server l'hai fatto tu o è sotto il tuo controllo? Perché comunque il certificato client andrà fatto firmare dalla CA sul server ovviamente per essere valido.

Prova a guardare qui:
http://www.codeproject.com/Articles/...h-Certificates