Попробуй в параметры функции mail() добавлять кое что вот так:
mail("ivan@ivanov.org","Привет","Как дела","From:
sidorov@sidor.net",
"Reply-to:
mail@mail.com",
"Content-Type: text/plain, charset=\"koi8-r\",
"Content-Transfer-Encoding: 8bit");
Нужно просто указывать кодировку и тип пересылаемого сообщения
(кодирование). Если не указать 8 бит то получиш транслитерицу, а если кодировку, то то что ты получаеш сейчас.
Хотя я моет и не прав.
Ты отпишись что как.
А вообще читай php.net про функцию которую используеш.