Can I change a custom post type label from a child theme?

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()
{
    $p_object = get_post_type_object( 'place' );

    if ( ! $p_object )
        return FALSE;

    // see get_post_type_labels()
    $p_object->labels->name="Locations";
    $p_object->labels->singular_name="Location";
    $p_object->labels->add_new            = 'Add location';
    $p_object->labels->add_new_item       = 'Add new location';
    $p_object->labels->all_items="All locations";
    $p_object->labels->edit_item          = 'Edit location';
    $p_object->labels->name_admin_bar="Location";
    $p_object->labels->menu_name="Location";
    $p_object->labels->new_item           = 'New location';
    $p_object->labels->not_found          = 'No locations found';
    $p_object->labels->not_found_in_trash="No locations found in trash";
    $p_object->labels->search_items="Search locations";
    $p_object->labels->view_item          = 'View location';

    return TRUE;
}