I found the solution:
Have You Found A Bug In MapKit? I Did. - JakeBehrens.com
Basically, set the MKMapView delegate to nil in dealloc.
mapView.delegate = nil;
I found that I also had to set
mapView.showsUserLocation = NO;
[mapView removeAnnotations:mapView.annotations];
If you're using location manager and its updating, set its delegate to nil in dealloc.
