custom post type permalinks プラグインで404エラー

その他にプラグインなどはインストールされていますか？

質問ばかりですみませんが、

• 一定時間で404になると言うことですが、そのときに、「カスタム分類のアーカイブのパーマリンクを変更する。」の値は変わっていますでしょうか？
• Custom Post Type Permalinksのバージョンはいくつでしょうか？

ということは、恐らく意図しないタイミングで、flush_rewrite_rulesが実行され、パーマリンクの再構築が発生しているということかと思います。
もし、functions.php等でflush_rewrite_rulesを記述している場合は、削除して下さい。

あと、プラグイン作っておいて言うのもなんですが、カスタムタクソノミーのパーマリンクを、

/case/case-cat/hogehoge/

とするだけであれば、register_taxonomyのパラメーターの $args[‘rewrite’][‘slug’]に /case/case-cat/を設定すれば、プラグインを使わなくても実現できます。

function case_postype() {
	$labels = array(
		'name'               => '事例',
		'singular_name'      => '事例',
		'add_new'            => '新規追加',
		'add_new_item'       => '新規事例を追加',
		'edit_item'          => '事例を編集',
		'new_item'           => '新規事例',
		'view_item'          => '事例を表示',
		'search_items'       => '事例を検索',
		'not_found'          => '投稿された事例はありません',
		'not_found_in_trash' => 'ゴミ箱に事例はありません。',
		'parent_item_colon'  => '',
	);
	$args   = array(
		'label'         => __( 'case' ),
		'labels'        => $labels,
		'public'        => true,
		'menu_position' => 5,
		'supports'      => array( 'title', 'author' ),
		'query_var'     => true,
		'hierarchical'  => false,
		'has_archive'   => true,
		'rewrite'       => array( 'slug' => 'case', 'with_front' => false ),
	);
	register_taxonomy(
		'case-cat',
		'case',
		array(
			'hierarchical'          => true,
			'update_count_callback' => '_update_post_term_count',
			'label'                 => '事例の種類',
			'public'                => true,
			'rewrite'               => array( 'slug' => 'case/case-cat', 'with_front' => false ),
			'show_ui'               => true
		)
	);
	register_post_type( 'case', $args );
}

add_action( 'init', 'case_postype' );