Comparing IDs in two arrays
The first thing we can do to improve the efficiency of this code is to remember to check for an error and make sure that the returned objects array returns anything before we do anything.  Generally, code from Apple libraries would guarantee our objects array to be empty if there were any sort of error, but some libraries don't make that guarantee.

We can also store our allAchievements locally as an NSDictionary rather than an array.  If allAchievements is an NSDictionary, our code looks something more like this:

[earnedQuery findObjectsInBackgroundWithBlock:^(NSArray *objects, NSError *error) {
    for (PFObject *earnedAchievement in objects) {
        Achievement *achievement = allAchievements[earnedAchievement[@"achievmentId"]];
        if (achievement) {
            achievement.earned = @YES;
            achievement.earnedDate = earnedAchievement[@"earnedOn"];
        }
    }
    [context save:&amp;error];
}];


Now we eliminate the nested loop.  And we only run through the outer loop once per earnedAchievement (which may be zero times).

Also, keep in mind that everything within the findObjectsInBackgroundWithBlock: is executing in the background.



Some other comments...

I would eliminate the use of magic strings.  Define all of your keys as constants somewhere.  This serves multiple purposes.


If we ever decide to actually change the key, it's changed everywhere all at once.
Typing magic strings is prone to typos, where as using a variable won't compile if we've made a typo (unless we typo into another variable name).
Typing magic strings won't auto-complete (which makes typos more likely, see point 2), but constant variables will.