Antes de ingresar un nuevo nombre de usuario (su email en este caso) siempre debes verificar que ese email ya no exista en la base de datos. Eso lo puedes hacer así:
Código PHP:
<?php
$consulta=mysql_query("SELECT email FROM usuarios WHERE email='$email_a_ingresar'");
$registro=mysql_fetch_row($consulta);
if($registro) { echo "Ese mail ya existe"; }
else
{ /* Sigues con el proceso de ingreso del nuevo usuario */ }
?>
Suponiendo que $email_a_ingresar tiene el email a comprobar, que la tabla se llama "usuarios" y que el campo donde estan los emails es "email".
Este código deberías ponerlo donde procesas los datos que vienen del formulario de registro, asi te aseguras que no se dejarán pasar registros cuyo email ya exista en la base de datos.
Saludos.