MKOverlayView performance

I am adding about 3000 MKOverlays to my map, and as you can imagine, it takes a while, up to about eight seconds sometimes. I'm looking for a way to use threading to improve performance, so the user can move the map around while overlays are being added. Preferably, the overlays would be added sequentially, starting with the just the ones within the map's region. I have tried something along these lines with GCD:

- (MKOverlayView*)mapView:(MKMapView*)mapView viewForOverlay:(id)overlay {
    __block MKPolylineView* polyLineView;

    //do the heavy lifting (I presume this is the heavy lifting part, but 
    // because this code doesn't compile, I can't actually *test* it)
    // on a background thread
    dispatch_async(backgroundQueue, ^ { 
        polyLineView = [[[MKPolylineView alloc] initWithPolyline:overlay] autorelease];
        [polyLineView setLineWidth:11.0];

        //if the title is "1", I want a blue line, otherwise red
        if([((LocationAnnotation*)overlay).title intValue]) {
            [polyLineView setStrokeColor:[UIColor blueColor]];
        } else {
            [polyLineView setStrokeColor:[UIColor redColor]];
        }

        //return the overlay on the main thread
        dispatch_async(dispatch_get_main_queue(), ^(MKOverlayView* polyLineView){
            return polyLineView;
        });
    });
}

But because GCD blocks are defined with void parameter and return types, this code doesn't work- I get an incompatible pointer type error on the return line. Is there something I am missing here, or another way to thread this? Or perhaps an entirely different way to improve the performance of the overlay-adding process? I appreciate any and all help!

Edit:

I have found that the problem is not where I actually add the overlays here:

for(int idx = 1; idx < sizeOverlayLat; idx++) {
    CLLocationCoordinate2D coords[2];
    coords[0].latitude = [[overlayLat objectAtIndex:(idx - 1)] doubleValue];
    coords[0].longitude = [[overlayLong objectAtIndex:(idx - 1)] doubleValue];

    coords[1].latitude = [[overlayLat objectAtIndex:idx] doubleValue];
    coords[1].longitude = [[overlayLong objectAtIndex:idx] doubleValue];

    MKPolyline* line = [MKPolyline polylineWithCoordinates:coords count:2];
    [line setTitle:[overlayColors objectAtIndex:idx]];

    [mapViewGlobal addOverlay:line];
}

Adding all 3000 takes maybe 100ms here. The part that takes a long time (I assume) is where I actually create the overlays, in the first method I showed.

There is a little gap between what you want and what the compiler can do. When you are calling dispatch_async, you are actually telling the CPU "here, have this chunk of code, and run it whenever you feel like it, not now, not blocking my user interface thread". But, your method has to return now. There is simply no way for you to create anything in a background thread, because you are going to have to wait for it anyway before mapView:viewForOverlay: returns, since it has to return something.

This method is not the place to use GCD or any background code. If your problem is the addition of a big number of overlays at once, I would split all the overlays into chunks of say 100 and add them to the map with a delay of 100ms between each batch.