Hola tu problema son las comillas ke utilizas en las variables ke estas enviando, prueba hacer lo esto modo:
Código:
//Datos de conexión a la base
$nombre=$_POST["nombre"];
$direccion=$_POST["direccion"];
$ciudad=$_POST["ciudad"];
$link= mysql_connect("localhost", "root","123456");
mysql_select_db("libreria",$link);
$inss="INSERT INTO Clientes (Nombre,Direccion,Ciudad) VALUES
('$nombre','$direccion','$ciudad')";
$result = mysql_query($inss) or die('Consulta fallida: ' . mysql_error());
Asegurate tambien de ke los nombre de los campos esten en el orden en ke los pones en el insert en la BD y ke tengan el mismo nombre (no es lo mismo Nombre ke nombre).
SALU2