Aqui logre resolverlo..........por si aalguien le hace falta
<?php
$query = mysql_query("SELECT newsleter FROM newsleter WHERE newsleter = '$newsleter'");
if($row=mysql_fetch_array($query)){
echo "<p align='center' class='style2'>Su mail ya esta en nuestra base de datos.</p>";
} else {
$sql = "INSERT INTO newsleter (newsleter, fecha) VALUES ('".$newsleter."', '".$fecha."')";
$result = mysql_query($sql);
echo "<p align='center' class='style2'>Tu E-mail se envio exitosamente!</p>";
}
?>