Contact Form 7

Hi All: I know this is not a plugin you support but I thought I would try to find a solution to a problem I am having.

1) Contact Form 7 Was installed and some custome forms were created
2) They were all tested before the DNS was pointing to the domain...A-OK
3) I made the website live yesterday and no forms work. Error reads "Failed to send your message. Please try later or contact the administrator by another method."

I believe the problem is DNS is not controlled by the hosting company. Any ideas for a work around or a better plugin for handling online form submissions?

Thanks,

Rob