I don't know if this can make a difference, but you could try to change the order in which you assign the style and color of the bar. Try:
myTopToolbar.barStyle = UIBarStyleDefault;
myTopToolbar.tintColor = [UIColor colorWithPatternImage:[UIImage imageNamed:NAVIGATION_BAR_BACKGROUND]];
It's possible that assigning the style after changing the tintcolor resets the color.
EDIT
Why this would affect only ios5 and not ios6 I don't know.