The issue really got me big time. I spent a long time trying to figure out what went wrong so I am hoping this post can help you.
Our Expense Claim workflow was unable to send out email notifications and the error message was "The email message cannot be sent. Make sure the outgoing email settings for the server are configured correctly"