Du var nära. Frågan ska vara så här:
db.test.update({"city":"Palo Alto"},{"$pull":{"friends":{"name":"Frank"}}});
$pull
tar ett objekt vars fält specificerar fältarrayen "friends"
. Värdet {"name":"Frank"}
representerar frågan (att köras inuti arrayen) för att hitta elementet som ska dras ut.