Mira yo sustituiria lo que tienes por esto:
Código PHP:
<html>
<head>
<title>Resultado de la insercion</title>
</head>
<body>
<h2>Resultado de la insercion</h2>
<?php
$conecta = mysql_connect("localhost","","") or die ("No puedo conectar a
la base de datos");
mysql_select_db("telefonos",$conecta);
$sentencia = "insert into listado (Nombre,Tel_casa,Tel_trabajo,Tel_celular,Domicilio
,Ciudad) VALUES ('$Nombre','$Tel_casa','$Tel_trabajo','$Tel_celula
r','$Domicilio','$Ciudad')";
mysql_query($sentencia,$conecta);
?>
<p>
<a href=insercion.html>Agregar Nuevo Registro
<p>
<a href=telefonos.html>Regresar al Menu Telefonos
</body>
</html>
checa tambien el tipo de datos que recibe cada campo .
espero te sirva de algo.