Modification to wp_list_categories

Move what you are calling the “standard link ending” to the end of the function, instead of the beginning.

class CategoryThumbnail_Walker extends Walker_Category {
    // A new element has been stumbled upon and has ended
    function end_el( $output, $category, $depth, $args ) {
        // Get one post
        $posts = get_posts( array(
            // ...from this category
            'category' => $category->cat_ID,
            'numberposts' => 1
        ) );
        // If a post has been found
        if ( isset($posts[0]) ) {
            // Get its thumbnail and append it to the output
            $featured = get_the_post_thumbnail( $posts[0]->ID, 'extrathumb', null );
            $output .= $featured;
        }

        // Output the standard link ending
        parent::end_el( $output, $category, $depth, $args );
    }
} 
wp_list_categories( 
  array(
    'show_count' => 1,
    'walker' => new CategoryThumbnail_Walker()
  ) 
); 

I believe that “nests” correctly (I didn’t analyze it very thoroughly though), but I am pretty sure you’d have a neater output by modifying the start_el method instead of the end_el one.