Customizing Category Widget

try to add something like this to functions.php of your theme:

add_filter('wp_list_categories', 'cat_count_span_inline');
function cat_count_span_inline($output) {
$output = str_replace('</a> (','<span> ',$output);
$output = str_replace(')','</span></a> ',$output);
return $output;
}

http://codex.wordpress.org/Plugin_API/Filter_Reference
http://codex.wordpress.org/Template_Tags/wp_list_categories

it will output your structure for all the wp_list_categories() in your theme, where ‘show post count’ is ticked.