Вы установили свои заголовки электронной почты?
// To send HTML mail, the Content-type header must be set
$headers = 'MIME-Version: 1.0' . "\r\n";
$headers .= 'Content-type: text/html; charset=iso-8859-1' . "\r\n";
// Mail it
mail($to, $subject, $message, $headers);
Если да, то есть ли у других почтовых клиентов такая же проблема?Или это просто Gmail?