Since the 3.3.3 and WP 3.5.1 update (either or both could be implicated, because they were updated at the same time) all Contact Form 7 forms return "Failed to send your message. Please try later or contact administrator by other way."
These forms have all been working on this site for several years without problems. No change has occurred to the AMP stack on the server. There has been no change to the theme, pages, plug-in settings or other content. There is no site cache enabled.
Contrary to the FAQ, there is no colored box around the message. It appears with no border, so that's not providing any useful information.