In order to decrypt someone's message, you need his public key. This element is automatically stored by Mail in your login keychain.
The fact that Mail is unable to decrypt the message may indicate that this public key is missing or has become corrupted. You may want to ask the sender to send you a signed message and to read it (even if it is blank).
That way, Mail will re-import the certificate and should be able to display the encrypted message correctly. For additional security, remove the old public key from the Keychain first.