Are you actually validating client identity with the SSL certificate rather than just using a server-side certificate and SSL to encrypt the communication? If so, that's not a particularly common scenario (although you may have very valid reasons for doing so). If you don't have a business need to authenticate clients with certificates, you could still encrypt communications while turning off client side certificate-based authentication which would solve your problem :)
According to the IIS Authentication documentation on MSDN:
IIS can also use SSL/TLS to
authenticate the client by requiring
the client to provide a certificate.
When requesting a client certificate,
the server provides the client with a
list of CAs that the server trusts.
This list is derived from the server's
Certificate Trust List (CTL). If the
client possesses a certificate issued
by a CA from the CTL, it sends a copy
of that certificate to the server for
verification. If the certificate is
valid, IIS authenticates the user that
maps to the provided certificate. As
such, you should limit the CTL on IIS
to those CAs you determine to be truly
trustworthy.
Is it at all possible that you have multiple CA's generating the client certificates, and for some reason one of them is not on the Server's Certificate Trust List (CTL)?