If you you receive error message - Your message was not sent, you need to check if email you used in your profile page (the one you use to login to admin) is bound to your domain name. So it should be real email account under your domain name. Such restrictions may take place if your hosting provider prevents sending emails from outside domains due to protection from fishing.
Just make sure you are using email account, which exists under your domain name.
If this error still persists you should try SMTP method for sending emails:
1. Please enable option Use SMTP Server (Simple Mail Transfer Protocol) in the "Mail" section under settings tab.
2. Just enter your SMTP settings:
SMTP server: mail.YOURDOMAIN.com
Autentification type: Login
Username: the email address you got with your hosting provider
Password: the password of your email box with your hosting account
Secure SMTP Connection: if required
If you don't have them or not sure where to get, you may simply contact your web hosting provider and they will give you this information.
3. Save changes, clear the cache in your browser and check Contact Form.
If you have any issues please submit a ticket.