I am using WP 3.3.1 and eStore Elegant Theme.
The contact form will not send messages. I ultimately changed the wp_mail() call in wp-content > estore > page-contact.php to the native PHP mail() (deleted the wp_) and not only did the message send correctly but the previous failed attempts all sent out as well.
It appears that the wp_mail() function uses mail() anyway via:
// Set to use PHP's mail()
Any help appreciated, although at present it is working with mail().