Reslug a Custom Post Type

I also created a similar approach as was mentioned by @sri, however using $wpdb vs wp_update_post should be more performant and configurable.

/**
 * Reset the slugs on a particular post type to use the default sanatized slugs
 * @param  string  $post_type         filter by post type
 * @param  int $offset                set the paginated post to start
 * @param  boolean $force_guid_update * WARNING * never enable this
 *
 * @example add the following code into your theme's functions.php file, ensure
 * that the desired post type is set when calling wp20140226_reset_slugs('post');
 * Then navigate to wp-admin/options-permalink.php to activate query to reset slugs.
 * Depending on how many posts need to be updated this method may take quite 
 * some time, on a shared host there may be a need to set the $offset argument
 * to limit the amount of time the script runs and use multiple calls by adjusting
 * the offset to progress through the entire record set.
 * 
 */
function wp20140226_reset_slugs( $post_type = null, $offset = 0, $force_guid_update = false ){
    global $pagenow, $wpdb;

    if ( $pagenow != 'options-permalink.php' || empty($post_type) )
        return;

    $get_post_args = array(
        'post_type' => $post_type, 
        'post_status' => 'any'
        );

    if( $offset == 0 ){
        $get_post_args['posts_per_page'] = -1;
    } else {
        $get_post_args['offset'] = $offset;
    }

    $posts_to_fix = new WP_Query( $get_post_args );

    foreach( $posts_to_fix->posts as $post_to_fix ){
        $wpdb->update( 
            $wpdb->posts, 
            array( 'post_name' => sanitize_title( $post_to_fix->post_title ) ), 
            array( 'ID' => $post_to_fix->ID ), 
            array( '%s' ), 
            array( '%d' ) 
        );
    }

    // you should really leave this alone (do not set to true unless you need to)
    //http://codex.wordpress.org/Changing_The_Site_URL#Important_GUID_Note
    if( $force_guid_update ){
        $siteurl = trailingslashit( get_option('siteurl') );
        $wpdb->query( "UPDATE {$wpdb->posts} SET guid = CONCAT( '{$siteurl}?p=', ID ) WHERE post_type = {$post_type} OR post_type="revision";" );
    }

    add_action('admin_notices', 'wp20140226_reset_slugs_admin_notice');

}

/**
 * notify the user when the reset slug queries are run
 */
function wp20140226_reset_slugs_admin_notice(){
    ?>
    <div class="updated">
        <p><?php _e('You have successfully run the reset slugs function, please disable or suffer impact when in the admin.'); ?></p>
    </div>
    <?php
}

wp20140226_reset_slugs('post'); // change this to be your custom post type

source: https://gist.github.com/codearachnid/9243595