カスタム投稿タイプのパーマリンク階層構造

よく見るとslug間違ってますねー。
これでどうでしょう？

'rewrite' => array(
    'slug' => 'test_cat',
    'hierarchical' => true
)

そういう時はこうしちゃいましょうー。

'rewrite' => array(
    'slug' => 'test_cat',
    'with_front' => false,
    'hierarchical' => true
)

あと、こういうのはCodexの関数リファレンスに大体書いてあるので、目を通してみると良いですよー。

私、最初に書かれていたパーマリンク構造をしっかり見ることが出来てませんでしたね。
申し訳ないですー。
多分これで解決すると思うので、お付き合いくださいー。
with_frontなんですけど、よーく見るとregister_post_typeの中にもありますよねー？
もうお分かりだと思いますけど、そこがfalseになっているので、trueにしてあげてくださいー。

酔いが回った状態で回答していました。
失礼しました。

そして今じっくり見直していて思ったんですけど、他にも間違ってるところありますね。

//'query_var' => false,
// falseではなくカスタム投稿タイプを指定
'query_var' => 'test'

//'query_var' => true,
// trueではなくタクソノミーを指定
'query_var' => 'test_cat',

一度そのコードはfunctions.phpから外してプラグインで設定した方が良いかもしれません。
渡すべきパラメータが足りないとか間違っているとか、そういう事が原因である可能性も十分あるので、まずはそこから潰していくと原因も特定しやすいと思います。

ちなみにプラグインはCustom Post Type Generatorが個人的におすすめです。
このプラグインで作成したカスタム投稿タイプやカスタムタクソノミーの設定をExportするとこういうコードが取得できます。
(プラグインで設定した内容によってパラメータは変化します)

function cptg_custom_post_types()
{
	$labels = array(
		'name' => 'テスト投稿タイプ',
		'singular_name' => 'テスト投稿タイプ',
		'menu_name' => 'テスト投稿タイプ',
		'name_admin_bar' => 'テスト投稿タイプ',
		'all_items' => '投稿一覧',
		'add_new' => '新規追加',
		'add_new_item' => '新規投稿を追加',
		'edit_item' => '投稿の編集',
		'new_item' => '新規投稿',
		'view_item' => '投稿を表示',
		'search_items' => '投稿を検索',
		'not_found' =>  '投稿が見つかりませんでした。',
		'not_found_in_trash' => 'ゴミ箱内に投稿が見つかりませんでした。',
		'parent_item_colon' => '親投稿',
	);
	$args = array(
		'labels' => $labels,
		'public' => true,
		'exclude_from_search' => false,
		'publicly_queryable' => true,
		'show_ui' => true,
		'show_in_nav_menus' => true,
		'show_in_menu' => true,
		'show_in_admin_bar' => true,
		'has_archive' => true,
		'menu_position' => null,
		'menu_icon' => null,
		'hierarchical' => false,
		'rewrite' => array( 'slug' => 'test','with_front' => true,'feeds' => true,'pages' => true ),
		'query_var' => 'test',
		'can_export' => true,
		'supports' => array( 'title','editor' ),
	);
	register_post_type( 'test', $args );

	$labels = array(
		'name' => 'テストタクソノミー',
		'singular_name' => 'テストタクソノミー',
		'menu_name' => 'テストタクソノミー',
		'all_items' => 'すべてのタグ',
		'edit_item' => 'タグの編集',
		'view_item' => 'タグを表示',
		'update_item' => 'タグを更新',
		'add_new_item' => '新規タグを追加',
		'new_item_name' => '新規タグ名',
		'parent_item' => '親カテゴリー',
		'parent_item_colon' =>  '親カテゴリー',
		'search_items' => 'タグを検索',
		'popular_items' => '人気のタグ',
		'separate_items_with_commas' => 'タグが複数ある場合はコンマで区切ってください',
		'add_or_remove_items' => 'タグの追加もしくは削除',
		'choose_from_most_used' => 'よく使われているタグから選択',
		'not_found' => 'タグが見つかりませんでした。',
	);
	$args = array(
		'labels' => $labels,
		'public' => true,
		'show_ui' => true,
		'show_in_nav_menus' => true,
		'show_tagcloud' => true,
		'meta_box_cb' => null,
		'show_admin_column' => true,
		'hierarchical' => true,
		'query_var' => 'test_cat',
		'rewrite' => array( 'slug' => 'test_cat','with_front' => true,'hierarchical' => true, ),
		'sort' => false,
	);
	register_taxonomy( 'test_cat', array( 'test' ) , $args );
}
add_action( 'init', 'cptg_custom_post_types' );

Exportで取得したコードをfunctions.phpに貼り付けてしまえば、その後はプラグインを無効にしても大丈夫です。

ただ、このプラグインは作者さんは日本の方なのですが、あえてパラメータを日本語に訳していないんですよね。
そんなわけなので、Codexのregister_post_typeやregister_taxonomyでそれぞれのパラメータを確認しながら設定を行った方が良いです。

まずパーマリンク構造を整理してみましょう。

Custom Post Type Permalinksで設定したパーマリンク構造
(分かりやすくするために%test_cat%を%custom_taxonomy%としています)

/%custom_taxonomy%/%postname%/

パーマリンク
/custom_post_type/term/post/
クエリ

post_type=custom_post_type&custom_post_type=post&name=post&custom_taxonomy=term

個別の投稿として有効なパーマリンク構造

パーマリンク
/custom_taxonomy/term/
クエリ

custom_taxonomy=term

タクソノミーアーカイブとして有効なパーマリンク構造

パーマリンク
/custom_post_type/custom_taxonomy/term/
クエリ

post_type=custom_post_type&custom_taxonomy=term

カスタム投稿内のタクソノミーアーカイブとして有効なパーマリンク構造

パーマリンク
/custom_post_type/term/
クエリ

name=term&category_name=custom_post_type

個別の投稿ではない
タクソノミーアーカイブではない
投稿を表示するリライトルール(/category/post/)が適用されるため正しく機能しない
適切なリライトルールがない無効なパーマリンク

個人的にはURLが少し短くなる程度のメリットしかないように感じるので、どのカスタムタクソノミーのタームなのかが分かるように/custom_post_type/custom_taxonomy/termで良いのではないかと思いますが、一応対応する方法も書いておきますね。

この無効なパーマリンクを有効にしたい時はadd_rewrite_ruleでリライトルールを追加します。
実際には次のようにして追加します。

function custom_rewrite_basic() {
  /**
   * パーマリンク
   * domain.com/custom_post_type/term
   *
   * custom_post_typeは実際に登録しているカスタム投稿タイプに置き換えてください
   * custom_taxonomyは実際に登録しているカスタムタクソノミーに置き換えてください
   * リライトルールを2つ追加していますが、これはページが分割されて表示される場合にも対応しなければいけないからです。
   */
  add_rewrite_rule( 'custom_post_type/(.+?)/page/?([0-9]{1,})/?$', 'index.php?post_type=custom_post_type&custom_taxonomy=$matches[1]&paged=$matches[2]', 'top' );
  add_rewrite_rule( 'custom_post_type/(.+?)/?$', 'index.php?post_type=custom_post_type&custom_taxonomy=$matches[1]', 'top' );
}
add_action( 'init', 'custom_rewrite_basic' );