When I upgraded my Ubuntu Linux from "Gutsy Gibbon" to "Hardy Heron" my gnome-terminal not shown some characters correctly anymore. I tried change the character encoding to UTF-8, but next time back again to ANSI_X3.4-1968. And I have found the solution.
Here is a simple UTF-8 mail sender function. This function also encode subject and plain-text message to UTF-8. If you need HTML mail sender, change the code in line 4 from text/plain to text/html, but this function is usable the most cases without any modification. I've used this function for webform and other web based mail notification.