I'm using following code (in C#) to change the color of the NavigationBar:
NavigationController.NavigationBar.SetBackgroundImage (new UIImage (), UIBarMetrics.Default);
NavigationController.NavigationBar.SetBackgroundImage (new UIImage (), UIBarMetrics.LandscapePhone);
NavigationController.NavigationBar.BackgroundColor = UIColor.Green;
The trick is that you need to get rid of the default background image and then the color will appear.