There is a global array $wp_post_types. You can change $wp_post_types[$post_type]->labels after the parent theme has set the CPT.
So … if the parent theme registers the CPT on 'init' like this:
add_action( 'init', 'register_my_cpt', 12 );
Then you need a later priority:
add_action( 'init', 'change_cpt_labels', 13 );
… or a later hook. I would use wp_loaded:
add_action( 'wp_loaded', 'change_cpt_labels' );
Example for custom post type place changed to location
add_action( 'wp_loaded', 'wpse_19240_change_place_labels', 20 );
function wpse_19240_change_place_labels()
{
global $wp_post_types;
$p = 'place';
// Someone has changed this post type, always check for that!
if ( empty ( $wp_post_types[ $p ] )
or ! is_object( $wp_post_types[ $p ] )
or empty ( $wp_post_types[ $p ]->labels )
)
return;
// see get_post_type_labels()
$wp_post_types[ $p ]->labels->name = 'Locations';
$wp_post_types[ $p ]->labels->singular_name = 'Location';
$wp_post_types[ $p ]->labels->add_new = 'Add location';
$wp_post_types[ $p ]->labels->add_new_item = 'Add new location';
$wp_post_types[ $p ]->labels->all_items = 'All locations';
$wp_post_types[ $p ]->labels->edit_item = 'Edit location';
$wp_post_types[ $p ]->labels->name_admin_bar = 'Location';
$wp_post_types[ $p ]->labels->menu_name = 'Location';
$wp_post_types[ $p ]->labels->new_item = 'New location';
$wp_post_types[ $p ]->labels->not_found = 'No locations found';
$wp_post_types[ $p ]->labels->not_found_in_trash = 'No locations found in trash';
$wp_post_types[ $p ]->labels->search_items = 'Search locations';
$wp_post_types[ $p ]->labels->view_item = 'View location';
}