How can I prompt the user to turn on location services after user has denied their use

With iOS8, you can finally link user to Settings app via openURL. For example, you can create a UIAlertView with a single button that takes user to the Settings app:

    UIAlertView *alert = [[UIAlertView alloc] initWithTitle:ICLocalizedString(@"LocationServicesPermissionTitle")
                                                    message:ICLocalizedString(@"LocationPermissionGeoFenceMessage")
                                                   delegate:self
                                          cancelButtonTitle:@"Settings"
                                          otherButtonTitles:nil];
    [alert show];

In your UIAlertView delegate:

- (void)alertView:(UIAlertView *)alertView clickedButtonAtIndex:(NSInteger)buttonIndex {
    [alertView dismissWithClickedButtonIndex:buttonIndex animated:YES];
    [[UIApplication sharedApplication] openURL: [NSURL URLWithString: UIApplicationOpenSettingsURLString]];
}

Update:

As of iOS 8, there is now the constant UIApplicationOpenSettingsURLString which represents a URL that, when opened, opens the Settings app to your application's settings (where the user can then re-enable location services).

Original:

There is no way for you to do this. Your only real option is to display an alert informing the user that your application requires location services, and instructing them to manually go to the Settings app and turn it on.

AlertViews are deprecated in iOS 8. There is now a better way to handle alerts using the new AlertController:

UIAlertController *alertController = [UIAlertController alertControllerWithTitle:NSLocalizedString( @"Enter your title here", @"" ) message:NSLocalizedString( @"Enter your message here.", @"" ) preferredStyle:UIAlertControllerStyleAlert];

UIAlertAction *cancelAction = [UIAlertAction actionWithTitle:NSLocalizedString( @"Cancel", @"" ) style:UIAlertActionStyleCancel handler:nil];
UIAlertAction *settingsAction = [UIAlertAction actionWithTitle:NSLocalizedString( @"Settings", @"" ) style:UIAlertActionStyleDefault handler:^(UIAlertAction *action) {
   [[UIApplication sharedApplication] openURL:[NSURL URLWithString:
                                                    UIApplicationOpenSettingsURLString]];
}];

[alertController addAction:cancelAction];
[alertController addAction:settingsAction];

[self presentViewController:alertController animated:YES completion:nil];

According to Apple's Docs on the locationServicesEnabled method.

The user can enable or disable location services from the Settings application by toggling the Location Services switch in General.

You should check the return value of this method before starting location updates to determine whether the user has location services enabled for the current device. If this method returns NO and you start location updates anyway, the Core Location framework prompts the user to confirm whether location services should be reenabled.

So cant you just start location services updates any way to cause the alert to be prompted?

Here is the swift 3 implementation of the code provided by Markus and bjc.

let alertController = UIAlertController(title: NSLocalizedString("Enter your title here", comment: ""), message: NSLocalizedString("Enter your message here.", comment: ""), preferredStyle: .alert)

let cancelAction = UIAlertAction(title: NSLocalizedString("Cancel", comment: ""), style: .cancel, handler: nil)
let settingsAction = UIAlertAction(title: NSLocalizedString("Settings", comment: ""), style: .default) { (UIAlertAction) in
                UIApplication.shared.openURL(NSURL(string: UIApplicationOpenSettingsURLString)! as URL)
            }

alertController.addAction(cancelAction)
alertController.addAction(settingsAction)
            self.present(alertController, animated: true, completion: nil)