So, as I mentioned in my comment I do think this is a bug but we'll see how Apple responds. But yeah, segues have no love for view controllers that are the root view controllers of multiple navigation controllers. There are a number of workarounds depending on the context under which it comes up.
Best workaround : Share the navigation controllers, not their root view controllers
So for the simple example given above you could do this and everything would be fine:

Other workaround : This one is more applicable to complex storyboards that may have different custom navigation controllers so that sharing the nav controller isn't possible. One hilarious aspect of this issue is that when a view controller has two parent nav controllers in the storyboard, you won't know until runtime which one gets it! And further, on different runs they can switch :P (another reason I think this is a bug).
Sooooo from within prepareForSegue you can check if your navigation controller got unpacked with a rootViewController and, if it didn't, force it in there yourself:
UINavigationController* nc = segue.destinationViewController ;
if (nc.viewControllers.count == 0) {
nc.viewControllers = @[[self.storyboard instantiateViewControllerWithIdentifier:@"MyDetailVC"]];
}