When I open the new file dialog I see only 3 Cocoa Touch Classes: Objective-C class, Objective-C test case class, UIViewController subclass. When I last worked with Xcode, before I updated it, I remember there were more than 3 options, which included what I'm looking for: UINavigationController.
So where can I find this template to create a UINavigatonController subclass?
Apple's made a lot of changes to Xcode's file creation screen and they've caught me of guard as well. I'm not exactly sure what your navigation controller is attempting to accomplish, but this post at the iPhoneDevSDK forum explains why you shouldn't subclass UINavigationController and instead present your view modally.
iPhoneSDK Forum UINavigation Controller Subclassing
In addition to the discussion in the forum about modal view controllers, here is source code from Apple's View Controller programming guide that explains how accomplish this.
YourViewController *viewController = [[YourViewController alloc] initWithNibName:@"YourView" bundle:nil];
viewController.delegate = self;
UINavigationController *navigationController = [[UINavigationController alloc] initWithRootViewController:viewController];
[self presentModalViewController:navigationController animated:YES];