Problema com caracteres especiais ao enviar email

Eu tenho um formulário simples de contato com envio dos dados por email, ele está funcionando bem a não ser pelos caracteres especiais que vêm desformatados (como no exemplo abaixo).

Assunto: Apresentação

O código PHP que estou utilizando peguei da Locaweb e fiz minhas alterações. No código já tem a parte do UTF8, mas ainda sim não funciona. Será que alguém consegue me ajudar, por favor?

Segue código completo abaixo.

<?php

/ Medida preventiva para evitar que outros domínios sejam remetente da sua mensagem. /

if (eregi('tempsite.ws$|locaweb.com.br$|hospedagemdesites.ws$|websiteseguro.com$|publiccloud.com.br$', $_SERVER[HTTP_HOST])) {
 $emailsender='#';
}

$emailsender='#' ;
}

/ Verifica qual éo sistema operacional do servidor para ajustar o cabeçalho de forma correta. /
if(PATH_SEPARATOR == ";") $quebra_linha = "\r\n"; //Se for Windows
else $quebra_linha = "\n"; //Se "não for Windows"

// Passando os dados obtidos pelo formulário para as variáveis abaixo

$contactName = $_POST['contactName'];
$contactEmail = $_POST['contactEmail'];
$contactDest = $_POST['contactDest'];
$contactSubject = $_POST['contactSubject'];
$contactMessage = $_POST['contactMessage'];

/ Montando a mensagem a ser enviada no corpo do e-mail. /

$mensagemHTML = '<div style="font-family: Arial; font-size: 12px; color: #0e0c49;">
<P><i>Esta é uma mensagem enviada através do site.</i></P> <hr>
<P><b>Nome do Remetente: </b></P>
<p style="padding-left: 20px; padding-right: 150px;">'.$contactName.'</p>
<P><b>E-mail: </b></P>
<p style="padding-left: 20px; padding-right: 150px;">'.$contactEmail.'</p>
<P><b>Destinatário: </b></P>
<p style="padding-left: 20px; padding-right: 150px;">'.$contactDest.'</p>
<P><b>Assunto: </b></P>
<p style="padding-left: 20px; padding-right: 150px;">'.$contactSubject.'</p>
<P><b>Mensagem: </b></P>
<p style="padding-left: 20px; padding-right: 150px;">'.$contactMessage.'</p>
<hr></div>';

/ Montando o cabeçalho da mensagem /

$headers = "MIME-Version: 1.1" .$quebra_linha;
$headers .= "Content-type: text/html; charset=iso-8859-1" .$quebra_linha;
$headers .= "From: " . $emailsender.$quebra_linha;
$headers .= "Reply-To: " . $contactEmail.$quebra_linha;

/ Enviando a mensagem /
//É obrigatório o uso do parâmetro -r (concatenação do "From na linha de envio"), aqui na Locaweb:
if(!mail($emailsender, $contactSubject, $mensagemHTML, $headers ,"-r".$emailsender)){ // Se for Postfix
$headers .= "Return-Path: " . $emailsender . $quebra_linha; // Se "não for Postfix"

 mail($emailsender, $contactSubject, $mensagemHTML, $headers );
}

/ Mostrando na tela as informações enviadas por e-mail /
{

echo "<script>window.location.href='#'</script>";
}
?>