Бил си близо. Заявката трябва да бъде така:
db.test.update({"city":"Palo Alto"},{"$pull":{"friends":{"name":"Frank"}}});
$pull взема обект, чието поле указва полето масив "friends" . Стойността {"name":"Frank"} представлява заявката (за изпълнение вътре в масива) за намиране на елемента за изтегляне.