WordPress custom permalinks, pages are now 404

You need to setup your permalinks for menutype using custom rewrite rules. What you’ve done is apply the menutype prefix to everything, even though menutype isn’t relevant to everything, so things are being misinterpreted.

You would need something similar to this:

function custom_rewrite( $wp_rewrite ) {
    $feed_rules = array(
        '([^/]+)(/[0-9]+)?/?$'    =>  'index.php?menu_type=". $wp_rewrite->preg_index(1)."&post_name=". $wp_rewrite->preg_index(2)

    $wp_rewrite->rules = $feed_rules + $wp_rewrite->rules;
// refresh/flush permalinks in the dashboard if this is changed in any way
add_filter( "generate_rewrite_rules', 'custom_rewrite' );

However, I would recommend you add a prefix such as ‘menus’ etc beforehand to prevent further clashes with the existing rewrite rules.

Use the monkeyman rewrite analyser tool plugin to test any rewrite rules you make/change/edit by putting in URLs and seeing which rules are activated and in which order.