I have raised a McAfee service request about this issue and got a response that contradicts this McAfee KB article.
The response was that the certicate must have the Data Encipherment key usage flag. Frankly, I don't understand this requirement since it makes most existing certificates useless for EERM recovery. For example, a user's Windows EFS certificate would be a good candidate for recovery as it is tied to an individual Windows login ID, but it's a key encipherment certificate. Similarly a user's digital signature certificate would be another good candidate, but again, it doesn't have the data encipherment flag. I have confirmed via testing that neither of these types of certificates are acceptable for EERM Allow User Certificate recovery.
As an aside, when we were intially deploying EEPC, we had some technical encryption questions of McAfee which they could not answer -- we were somewhat surprised (understatement) to be told that McAfee does not employ any cryptographers. I suspect this strange certificate usage requirement is a symptom of this.
Another Update: Service Request has been resolved, and the KB article updated. Currently both Key and Data Encipherment must be specified in order to use a certificate for recovery, but McAfee will look into supporting just Key Enchiperment in later releases, but no ETA.