I was missing one thing. In setEditing:, instead of calling reloadData I should have done:
- (void)setEditing:(BOOL)editing animated:(BOOL)animated {
[super setEditing:editing animated:animated];
[self.tableView setEditing:editing animated:animated]; // not needed if super is a UITableViewController
NSMutableArray* paths = [[NSMutableArray alloc] init];
// fill paths of insertion rows here
if( editing )
[self.tableView insertRowsAtIndexPaths:paths withRowAnimation:UITableViewRowAnimationBottom];
else
[self.tableView deleteRowsAtIndexPaths:paths withRowAnimation:UITableViewRowAnimationBottom];
[paths release];
}