Among other possible causes including your hoster's settings you can get this error if your site name (Configuration->Site Information->Site name) contains non-English characters. Specifically because Drupal (as of version 7.14) handles [site:name] token incorrectly when constructing subject field for outgoing emails.
