I'm running Akismet 2.5.9 and WP 3.8. I've been experiencing this issue on and off for about a week. I get the following message:
The key below was previously validated but a connection to akismet.com can not be established at this time. Please check your server configuration.
I've verified with my host company that everything is working on their end. They sent me the following email: "Confirmed that all IP address of akismet is whitelisted in server. Also there is no block for outgoing requests in port 80. The php setting allow_url_fopen is also enabled for your account. There is no server settings blocking this connections. When I researched further I found that there is some issues with API upgrade of akimset."
Also, the rate of spam comments is ridiculous. They're coming in every couple of minutes.