I also tried setting up using the SMTP server method, and received the following in the logs:

Mail Exception Occurred. Unable to send mail: Connection refused
#0 /home1/imclient/public_html/in-marketing/concrete/libraries/3rdparty/Zend/Mail/Protocol/Smtp.php(167): Zend_Mail_Protocol_Abstract->_connect('tcp://auth.smtp...')
#1 /home1/imclient/public_html/in-marketing/concrete/libraries/3rdparty/Zend/Mail/Transport/Smtp.php(199): Zend_Mail_Protocol_Smtp->connect()
#2 /home1/imclient/public_html/in-marketing/concrete/libraries/3rdparty/Zend/Mail/Transport/Abstract.php(348): Zend_Mail_Transport_Smtp->_sendMail()
#3 /home1/imclient/public_html/in-marketing/concrete/libraries/3rdparty/Zend/Mail.php(1194): Zend_Mail_Transport_Abstract->send(Object(Zend_Mail))
#4 /home1/imclient/public_html/in-marketing/concrete/core/helpers/mail.php(349): Zend_Mail->send(Object(Zend_Mail_Transport_Smtp))
#5 /home1/imclient/public_html/in-marketing/concrete/core/controllers/blocks/form.php(454): Concrete5_Helper_Mail->sendMail()
#6 /home1/imclient/public_html/in-marketing/concrete/core/models/block.php(411): Concrete5_Controller_Block_Form->action_submit_form()
#7 /home1/imclient/public_html/in-marketing/concrete/startup/process.php(297): Concrete5_Model_Block->passThruBlock('submit_form')
#8 /home1/imclient/public_html/in-marketing/concrete/dispatcher.php(244): require('/home1/imclient...')
#9 /home1/imclient/public_html/in-marketing/index.php(2): require('/home1/imclient...')
#10 {main}

You should talk to your host service technical support and see if there are any restrictions on sending mail for your web server.

Well that thoroughly confused them. They now want me to send them the script being used to send mail so they can check to see if there are any restrictions

I am having this same problem. I have 3 different accounts with Bluehost and multiple concrete5 installs on each. I have no issues with sending mail via contact forms on 2 of the accounts but have the problem with the third. I asked support about it and they are saying it is a problem in the script. Have you had any success yet?

Having same issue. Seems to have started when we changed hosting to GoDaddy. Called them to make sure there we no restrictions on the account and they said none. I have tried several different outgoing servers and still cannot get the emails to send successfully. Have you resolved your issue (and how?).

Thanks!
Bruce

After doing an update to the site it started working.