Recaptcha is down for some users. / Down when this was posted.
Users of version 1.3 of this plugin might be having trouble due to server issues with recaptcha. It is down at the time of this post and has been for more than 12 hours now.
As a temporary fix: Uninstall/delete version 1.3 - Upload/install version 1.2
Or change in plugins/recaptcha/codebase.php this:
See the Google Group reCaptcha pages for more info.http://groups.google.com/group/recaptcha
Update: The service is back up. There is no need to modify the plugin now.
See the link above if you have trouble in the future.
For power users: The script recaptcha_ajax.js
can be self-hosted. It is not recommended in case the script is updated. See the link above, I got a reply from their support stating the same.