At the end of the day, Apple’s suggestion of removing location from UIBackgroundModes fixed our battery drain issue.
In order to still get locations in the background we had to wrap the [locationManager startLocationUpdates] & [locationManager stopLocationUpdates] calls with:
[[UIApplication sharedApplication] beginBackgroundTaskWithExpirationHandler];
[[UIApplication sharedApplication] endBackgroundTask:];