Your replacement code is incorrect, and thus illustrates the problem that Apple is trying to prevent. Here is your code:
self.navigationController = [[UINavigationController alloc]
initWithRootViewController:rootViewController];
[self.view addSubview:[navigationController view]];
[navigationController release];
You left out the "self." in your references. Perhaps you meant to access the ivar directly, but in that case you have created very confusing code by mixing accessors and direct ivar access (and violated the cardinal rule by using direct ivar access outside an accessor). If not, then you meant to write this:
self.navigationController = [[UINavigationController alloc]
initWithRootViewController:rootViewController];
[self.view addSubview:[self.navigationController view]];
[self.navigationController release];
That last line is very wrong. Never send -release to the result of a method call. So no, the way you're doing it isn't correct.
That said, Apple and I disagree on how to do this. Here's how I do it:
self.navigationController = [[[UINavigationController alloc]
initWithRootViewController:rootViewController] autorelease;
[self.view addSubview:[self.navigationController view]];
I like -autorelease because I find it prevents errors. The further apart the alloc and release get, the more likely a developer will inject a memory leak (by adding a "return" for instance). autorelease avoids this by keeping the retain and release together, making the intent to use this as a temporary variable more clear, and generally makes code review much easier.
Apple tends to disagree with me in their example code because they're emphasizing performance by using release versus autorelease. I find this to be the wrong optimization, since this object won't be deallocated during this run loop in either case (so no memory is saved), and I believe the very small performance penalty of autorelease is more than made up for by the reduction in memory leaks due to incorrect use of release.
The autorelease vs. release debate is filled with shades of gray (I certainly use release directly in loops), and different developers have different approaches, but your replacement code isn't the right way to do it in either case.