Every other PGP/GPG-encrypted message I've ever received marked the encrypted portion with the content-type 'application/pgp-encrypted', and the signature 'application/pgp-signature'.
\r\n\r\nYours appears to have done neither. Perhaps some clients sniff for the 'BEGIN PGP MESSAGE' line, and Evolution doesn't?
\r\n\r\nSaving the message and decrypting on the command line worked OK.