I have been fighting with NSFetchedResultsController. After some struggles, I think I have finally made peace with it.
If you want to save yourself some hassle, replace your current Navigation-Based Core Data Application Xcode project with this one. Unzip and copy the folder to this location, replacing the one that's there:
/Developer/Platforms/iPhoneOS.platform/Developer/Library/Xcode/Project Templates/Application/Navigation-based Application/