то что помню, так это во-первых надо передавать два раза заголовок о кодировке.и один из них должен быть ранее заголовка subject
щаз немного пороюсь у себя, и кину код ф-ции отправки
UPDATE:
должно получится что-то на манер
$mail='email@host.com';
$message=
"Content-Type: text/plain; charset:utf-8\n".//один заголовок первым
"From: Лист рассылки\n".
"To: Иванов Иван Иванович\n".
"Subject: Пробная рассылка\n".
"Content-Type: text/plain; charset:utf-8\n".//и один заголовок последним
"\n".
"Текст самого письма";
mail($mail,'','',$message);