I’m using my custom wordpress theme. I had this same issue.
After few days of pain I decided to change my theme to standard WP theme(twenty ninety). reCaptcha appeared and form start working.
So first you should do is change your custom theme to one of wp standard themes. If recaptcha works and the form does not give an error, then the problem is in your theme.
In my case I forgot to add wp_footer(); in footer.php file
If not… Well… Pray to the Dark Lord
