Ao alterar a imagem de fundo de uma UINavigationBar, é importante fazer isso durante viewWillAppear ou viewWillDisappear. Tentei configurá-lo durante a inicialização do novo ViewController que estava colocando na pilha e não funcionou.
- (void)viewWillAppear:(BOOL)animated {
[self.navigationController.navigationBar setBackgroundImage:[UIImage imageNamed:@"NavigationImage.png"] forBarMetrics:UIBarMetricsDefault];
}