Tu étais proche. La requête devrait ressembler à ceci :
db.test.update({"city":"Palo Alto"},{"$pull":{"friends":{"name":"Frank"}}});
$pull prend un objet dont le champ spécifie le tableau de champs "friends" . La valeur {"name":"Frank"} représente la requête (à exécuter dans le tableau) pour trouver l'élément à extraire.