NSPredicate должен работать нормально, я пробовал это:
NSMutableArray *a = [NSMutableArray array];
[a addObject:[NSDictionary dictionaryWithObjectsAndKeys:@"North", @"Area", @"North", @"Test", nil]];
[a addObject:[NSDictionary dictionaryWithObjectsAndKeys:@"South", @"Area", @"North", @"Test", nil]];
[a addObject:[NSDictionary dictionaryWithObjectsAndKeys:@"East", @"Area", @"North", @"Test", nil]];
NSPredicate *p = [NSPredicate predicateWithFormat:@"%K matches %@", @"Area", @"North"];
NSArray *newArray = [a filteredArrayUsingPredicate:p];
NSLog(@"newArray:%@", [newArray description]);
Работает.