This is a known, reported WordPress bug.
There are some workarounds, such as this one:
add_action( 'edited_term_taxonomy','wpse26548_edited_term_taxonomy', 10, 2 );
function wpse26548_edited_term_taxonomy($term,$taxonomy) {
global $wpdb,$post;
//in quick edit mode, $post is an array()
//in full edit mode $post is an object
if ( is_array( $post ))
$posttype=$post['post_type'];
else
$posttype=$post->post_type;
if ($posttype) {
$DB_prefix=$wpdb->get_blog_prefix(BLOG_ID_CURRENT_SITE);
$sql = "UPDATE ".$DB_prefix."term_taxonomy tt
SET count =
(SELECT count(p.ID) FROM ".$DB_prefix."term_relationships tr
LEFT JOIN ".$DB_prefix."posts p
ON (p.ID = tr.object_id AND p.post_type="".$posttype."" AND p.post_status="publish")
WHERE tr.term_taxonomy_id = tt.term_taxonomy_id)
WHERE tt.taxonomy = '".$taxonomy->name."'
";
$wpdb->query($sql);
}
}
You may also need to add the following to your register_taxonomy()
arguments array:
'update_count_callback' => '_update_post_term_count'
Note that these are completely untested.
(See also: this related WPSE question)