Determine Whether Client Computers Are Ready for Native Mode

To help you determine if Configuration Manager 2007 client computers have a valid certificate for successful native mode communication before you migrate the site into native mode, run a utility called the Configuration Manager Native Mode Readiness Tool...

Error signing client message (0x80004005) in ClientAuth.log

Yesterday I come across a native mode client which was not communicating with MP. When I check the Clientauth.log I noticed the following error. 

Error signing client message (0x80004005).
RegTask: Failed to get certificate. Error: 0x80004005

I found that there were two client authentication certificates which match the certificate selection criteria. I removed one certificate from the client and the client started working properly. You can alternatively configure the site or the client installation properties to select any certificate that matches the creteria to fix this issue.