We are having the same problem/error message. It started at the same time as the report above (around 5/9/2013)
We have tried a few things, none of which solved the problem.
I’ve reinstalled our Akismet key
I’ve upgraded to the most recent version of Akismet (2.5.7)
I’ve checked all our setting as instructed.
We are using inmotion hosting. It looks like it may be a hosting issue. Are you by chance using inmotion too?