Varias anotaciones:
- Hay una FAQ que trata tu consulta

. Se titula "Cómo evitar repetir registros en mi BD", se basa en lo mismo: buscar la existencia de dichos registros.
- Ponle "prioridades" a los procesos de tu script. Primero consultas en la BD y después validas si los datos existen... pero si no existiesen ¿qué buscas entonces?; primero ve que haya datos, después buscalos

.
- Cuando valides si un campo no viene vacio, hazlo sobre el $_POST no sobre una variable a la que le asignas dicho valor... lo mismo que lo anterior: si $_POST['algo'] viene vacio ¿qué asignas entonces?

.
Código PHP:
if(!empty($_POST['algo'])) // si no esta vacio
$algo= $_POST['algo']; // entonces sí
- La función mysql_fetch_array() es para recuperar datos... ¿y si no se encontraron? (lo mismo). En su lugar usa
mysql_num_rows() (en la FAQ que mencioné) de la sig manera:
Código PHP:
$busqueda= mysql_query("SELECT ... etc");
if(mysql_num_rows($busqueda)>0 ) { // ó igual/diferente de 0... como lo quieras ver
echo "Los datos ya existen";
}
-

Ve que usé
mysql_query() y no mysql_db_query() como tú... no es necesario emplear esta última función pués antes ya hiciste el respectivo mysql_select_db(). Al usar solo mysql_query() separas procesos y en caso de error podrás identificar (si así lo indicas) si fue en la selección de la BD ó en la query...
-

... jejeje, tienes esto:
Código PHP:
$email=$_POST['apellido'];
¿apellido ó mail??, ¿así es?.. antes ya ocupaste "apellido"

.
Saludos!