I've seen this a few times on both the market and the forums. One thing I would try is pasting the PGP message into notepad or something and see if there are spaces before each line. I've had to manually go through each line and remove those before I could get a successful decryption.