Du warst nah. Die Abfrage sollte wie folgt aussehen:
db.test.update({"city":"Palo Alto"},{"$pull":{"friends":{"name":"Frank"}}});
$pull nimmt ein Objekt, dessen Feld das Feldarray "friends" angibt . Der Wert {"name":"Frank"} stellt die Abfrage dar (die innerhalb des Arrays ausgeführt wird), um das herauszuziehende Element zu finden.