I had the same error message, but also with Thunderbird and Enigmail on Linux. This seems to be more of a key server problem. After I changed it to hkp://pgp.uni-mainz.de in the keychain settings, it worked.
With the SKS-Keyserver I got the message like you did, with two of them it was said that they were faulty and with the third it worked then.
Possibly a compatibility problem? Sometimes it's really not easy to use PGP.