Je was dichtbij. De vraag zou als volgt moeten zijn:
db.test.update({"city":"Palo Alto"},{"$pull":{"friends":{"name":"Frank"}}});
$pull neemt een object waarvan het veld de veldarray specificeert "friends" . De waarde {"name":"Frank"} vertegenwoordigt de query (om binnen de array te draaien) om het element te vinden dat eruit moet worden gehaald.