I've been having this problem recently too. Akismet used to work fine for me. Now it is missing a lot of spam. I have gotten the error above and this morning after getting emailed about 608 spam I checked Akismet and saw:
"The key below was previously validated but a connection to akismet.com can not be established at this time. Please check your server configuration."
but below that it says:
"All Akismet servers are available"
Much of the time Akismet is working and it has worked fine for years so I don't think there is any problem with my host setup. Rather it appears to that the Akismet servers are intermittently down. This isn't a one time thing but has been happening time-to-time for weeks.
I love the assistance Akismet gives when it works. Hope it gets back to business and smooths out soon.