Bueno... el mensaje de que te ha insertado correctamente... sale sí o sí segúj el código que has puesto.
Mira... para ver los errores de Mysql agrega el die(mysql_error()).... en las líneas... también sería bueno que guardes el id de conexión en una variable para incluirlo en los mysql_query....
Tú código debería quedar así:
Código PHP:
<?
//Conexion con la base
$con=mysql_connect("localhost","","") or die("Error en la conexión :".mysql_error());
//Eliges la BD
mysql_select_db("ejemplo", $con) or die("Error en la seleccion de la BD :".mysql_error());
//Guardas la sentencia sql en una variable
//Esto se suele hacer para verificar que esté bien escrita con un "echo"
$sql="insert into clientes (nombre,telefono) values ('$nombre','$telefono')";
//Ejecucion de la sentencia SQL
mysql_query($sql, $con) or die("Error en la consulta :".mysql_error());
?>
... y si hay algún error en Mysql pa insertar o pa conectarse, el script detendrá su ejecución y te avisará del error...
Saludos