primero descarta que se halla enviado bien el mail.
Código PHP:
$envioOK = mail($nombre, $mail_to, $subject, $txt, $cabeceras);
if($envioOK){
header("Location: gracias.html");
}
else{
echo '<div style="color: red">Error Envio <br/></div>';
}
Igual, una buena practica seria usar una libreria como por ejemplo phpmailer.