Custom permalinks

Yes, this is possible, because your genres structure is /music/genres/[genre-name]. If it was /music/[genre-name] it would be complicated because it would conflict with /music/[post-name].

You just have to keep the order in mind. The rewrite rules should be ordered from most specific to least specific. If you first register the post type and then the taxonomy, the post type rules will come first. The problem is that the post type rules contain a very generic rule to match attachments, and this would mess with our taxonomy terms. But it will work if you first register the taxonomy and then the post type.

The confusing thing is that you normally pass the post types that will use the taxonomy you are registering, but you can just pass the empty array and make the connection later.

add_action( 'init', 'wpse13608_init' );
function wpse13608_init()
{
    register_taxonomy(
        'music-genre',
        array(),
        array(
            'rewrite' => array(
                'slug' => 'music/genre'
            ),
        )
    );
    register_post_type( 'music' );
    register_taxonomy_for_object_type( 'music-genre', 'music' );
}

You can verify this and play with your rules with my Rewrite analyzer plugin.