la forma de verificar datos es sencilla , hazlo con mysql_num_rows() que te busca el numero de registros que te salen de una consulta
Código PHP:
//recojes el numero de celular:
$celular = $_POST['celular'];
$sql="select * from celular where cel_numero=".$celular;
$rs=mysql_query($sql);
//traes el número de registros que da la consulta
$existe=mysql_num_rows($e_sql);
//SI TE SALE 1 ES PORQUE HAY UN REGISTRO... SI SALE 0 PORQUE NO EXISTE
if($existe==0){
//guardas el celular con el dato que tienes $celular
}
else{
//mandas el error que quieres
}
espero entiendas esta logica que es muy simple.
P.d. : si no se ajax... estoy condenado?