Código PHP:
$telefono="4294630";//variable que tendra el nuevo telefono
$rs=mysql_query("select * from tabla where telefono='$telefono'");//obtener la cantidad de registros que tengan el telefono
if(mysql_num_rows($rs)<=0){
mysql_query("insert into tabla values('campo1','campo2','campo3')");//insertamos el nuevo registro
}else{
echo "el telefono ya existe";//nostramis un mensaje
}
Suerte.