Você estava perto. A consulta deve ficar assim:
db.test.update({"city":"Palo Alto"},{"$pull":{"friends":{"name":"Frank"}}});
$pull pega um objeto cujo campo especifica o array de campos "friends" . O valor {"name":"Frank"} representa a consulta (a ser executada dentro do array) para encontrar o elemento a ser retirado. 
