MKReverseGeocoder is a great class, but sometimes may return the error:
Error Domain=PBRequesterErrorDomain Code=6001 "Operation could not be completed. (PBRequesterErrorDomain error 6001.)
luvieere's suggestion above are a great place to start, which is what I did as an example using the Google HTTP reverse geocoder. Here's my implementation of a GoogleReverseGeocoder class I wrote. The full explanation of how to use it can be found HERE.
// Send Google A Request
NSString *urlString = [NSString stringWithFormat:@"http://maps.google.com/maps/geo?q=%lf,%lf&output=csv&sensor=false",self.locationToGeocode.coordinate.latitude,self.locationToGeocode.coordinate.longitude];
NSURL *urlFromString = [NSURL URLWithString:urlString];
NSStringEncoding encodingType = NSUTF8StringEncoding;
NSString *reverseGeoString = [NSString stringWithContentsOfURL:urlFromString encoding:encodingType error:nil];
// Parse Out Response
NSArray *listItems = [reverseGeoString componentsSeparatedByString:@","];
NSArray *tempAddressArray = [[listItems objectAtIndex:2] componentsSeparatedByString:@"\""];
NSArray *tempCountryArray = [[listItems objectAtIndex:[listItems count]-1] componentsSeparatedByString:@"\""];
// Did Google Find Address? 200 is yes
if ([[listItems objectAtIndex:0] intValue] == 200)
{
// Set Class Member Variables
[self setGoogleReturnDidFindAddress:YES];
[self setGoogleReturnAddress:[tempAddressArray objectAtIndex:[tempAddressArray count]-1]];
[self setGoogleReturnCountry:[tempCountryArray objectAtIndex:0]];
[self setGoogleReturnCode:[[listItems objectAtIndex:0] intValue]];
[self setGoogleReturnAccuracy:[[listItems objectAtIndex:1] intValue]];
} else if ([[listItems objectAtIndex:0] intValue] > 600)
{
[self setGoogleReturnDidFindAddress:NO];
}