This is a terrible hack but, when placed in -viewDidAppear: method(s), it will change the background color (tint, actually) of UINavigationButtons. 
UINavigationBar *navBar = [[self navigationController] navigationBar];
for (UIView *subview in [navBar subviews])
    {
    if ([NSStringFromClass([subview class]) isEqualToString:@"UINavigationButton"])
        {
        if (![[subview title] isEqualToString:@"Done"])
            [subview setTintColor:[UIColor colorWithRed:255.0/255.0 green:0.0/255.0 blue:0.0/255.0 alpha:1.0]];
        }
    }
It will not however change tint for UINavigationItemButtonViews - and this is what is used for the navigation back buttons. If someone finds a way to affect them, please let me know.