Hmmmm.. Si lo estas haciendo tal cual lo pusiste en tu mensaje. Definitivamente hay algunos errores
que no te estan permitiendo hacer lo que necesitas, prueba usando el siguiente ejemplo.
Código PHP:
<?php
// creamos arreglo agenda
$agenda = array();
// creamos el arreglo cliente
$cliente = array( 'Nombre' => 'Marta',
'Apellido' => 'Macal',
'Telefono' => '47857878',
'mail' => '[email protected]');
// Lo agregamos al arreglo agenda
array_push( $agenda, $cliente );
//vemos la estructura del arreglo
print_r( $agenda );
?>