Estabas cerca. La consulta debería ser así:
db.test.update({"city":"Palo Alto"},{"$pull":{"friends":{"name":"Frank"}}});
$pull toma un objeto cuyo campo especifica la matriz de campos "friends" . El valor {"name":"Frank"} representa la consulta (para ejecutar dentro de la matriz) para encontrar el elemento para extraer.
