I was getting the message
"Failed to send your message. Please try later or contact administrator by other way"
in a red bordered box when trying to submit a wordpress form using Contact Form 7 plugin. There are many, many ways this vague error message can be displayed.
You could try installing an SMTP plugin as mentioned on a ton of sites.
Maybe you need to change the name of the address it is being sent from as mentioned by jevin.
Or as it was in my case someone put multiple email addresses and separated them with a semicolon instead of a comma and did not test the form. When putting multiple email addresses in the to field of the form you must be in the format