I couldn't add an accessibility label, but I found a workaround:
I replace the navigationItem's title View with a UILabel that has accessibility set up.
UILabel *titleLabel = [[UILabel alloc] init];
titleLabel.text = @"myTitle";
[titleLabel setAccessibilityLabel:@"myCustomAccessiblityLabel"];
[titleLabel setFont:[UIFont boldSystemFontOfSize:20.0]];
[titleLabel setBackgroundColor:[UIColor clearColor]];
[titleLabel setTextColor:[UIColor whiteColor]];
[titleLabel sizeToFit];
self.navigationItem.titleView = titleLabel;
I'm not sure why setting the accessibility label doesn't work, but the above code works for my needs.