I had almost exactly this problem, until I found the hint in a very recent blog post at iphone incubator
NSFetchedResultsController is caching the first results. (You probably have something set at initWithFetchRequest:managedObjectContext:sectionNameKeyPath:cacheName)
I’m guessing your code (like mine) is a derivation of the CoreData sample, so assuming it’s @”Root”, before you change the predicate, do a
[NSFetchedResultsController deleteCacheWithName:@"Root"];