Rewrite rules for custom posts types

So I created a new post type ‘quote’.
Basically I want to change all quotes URLs to domain.com/quotes/ID since as it as right now (/?quote={xxx}) could get pretty long, and since this post type is user-input-based, I don’t want to take any risks.

So I tried looking for answers… I found a really good tutorial that seemed to partially work. The urls did change, but I ever since I get a 404 page not found error.
Then, I tried looking for solutions. I tried some like adding flush_rewrite_rules(), opening the permalinks page in wordpress admin and press “save”, changed my code and changed the slug in the rewrite attribute of the post type. As you can guess, nothing worked.

function my_custom_post_type() {
    $labels = array(
              // too long
    );
    $args = array(
        'labels'        => $labels,
        'description'   => 'Holds our quotes and quotes specific data',
        'public'        => true,
        'menu_position' => 5,
        'capability_type' => 'post',
        'publicly_queryable' => true,
        'supports'      => array( 'editor', 'comments' ),
        'has_archive'   => true,
        'rewrite'   => false,
        'query_var'     => true,
    );

    register_post_type( 'quote', $args );
    flush_rewrite_rules();  //one of the solutions I found

    global $wp_rewrite;
    $projects_structure = '/quotes/%post_id%';
    $wp_rewrite->add_rewrite_tag("%quote%", '([^/]+)', "quote=");
    $wp_rewrite->add_permastruct('quote', $projects_structure, false);

    add_filter('post_type_link', 'quote_permalink', 10, 3); //translate the structure variables.
}

add_action( 'init', 'my_custom_post_type' );

In short, I do get forwarded to /quotes/ID/, but the page results in a 404 error.
I did try to look up answers but nothing really worked for me.
Hopefully someone could pinpoint the problem.