The short answer is that modifying the structure of the UINavigationBar is not supported by Apple. They really do not want you do be doing what you are trying to do. That is what is causing the issue you are seeing.
Please file a radar requesting this feature so that it can get enough attention to be officially added at some point.
Having said that, to solve the issue you can add a category to UINavigationBar with a -drawRect: method and draw the background image in that method. Something like this will work:
- (void)drawRect:(CGRect)rect
{
static UIImage *image;
if (!image) {
image = [UIImage imageNamed: @"HeaderBackground.png"];
if (!image) image = [UIImage imageNamed:@"DefaultHeader.png"];
}
if (!image) return;
CGContextRef context = UIGraphicsGetCurrentContext();
CGContextDrawImage(context, CGRectMake(0, 0, self.frame.size.width, self.frame.size.height), image.CGImage);
}