Hey, I had a bunch of trouble with contact form 7 not wanting to send emails with php_mail(). Also couldn't get it to work with this plugin.
After trying every fix I could online I stumbled upon a comment on another forum that suggested the problem was in the set up of comment form 7, not with wordpress.
I want everyone who is getting this " Failed to send your message. Please try later or contact administrator by other way. " in a red box, to check the contact form settings. The to: , from: and message fields need to be set for the form to capture the data and send it off.
mine look like this. To: (whatever email you want it sent to) From: [your-email] **very important** , Message Body: [your-message] ** also important if you want to get their message.