Custom Post Type / Taxonomy Slug / Post Title with post type archive

Replace your code with the following.
I have made some changes to the post_type_link filter’s callback function.

function my_custom_post_work() {
    $labels = array(
        'name'               => _x( 'Work', 'post type general name' ),
        'singular_name'      => _x( 'Work', 'post type singular name' ),
        'add_new'            => _x( 'Add New', 'book' ),
        'add_new_item'       => __( 'Add New Work' ),
        'edit_item'          => __( 'Edit Work' ),
        'new_item'           => __( 'New Work' ),
        'all_items'          => __( 'All Work' ),
        'view_item'          => __( 'View Work' ),
        'search_items'       => __( 'Search Work' ),
        'not_found'          => __( 'No work found' ),
        'not_found_in_trash' => __( 'No work found in the Trash' ), 
        'parent_item_colon'  => '',
        'menu_name'          => 'Our Work'
    );
$args = array(
        'labels'        => $labels,
        'description'   => 'Holds our works and work specific data',
        'public'        => true,
        'menu_position' => 5,
        'supports'      => array( 'title', 'editor', 'thumbnail', 'excerpt', 'comments' ),
        'has_archive'   => true,
        'rewrite'       => array( 'slug' => 'our-work/%work_category%')
    );
    register_post_type( 'work', $args );    
}
add_action( 'init', 'my_custom_post_work' );

function mav_taxonomies_work() {
    $labels = array(
        'name'              => _x( 'Work Categories', 'taxonomy general name' ),
        'singular_name'     => _x( 'Work Category', 'taxonomy singular name' ),
        'search_items'      => __( 'Search Work Categories' ),
        'all_items'         => __( 'All Work Categories' ),
        'parent_item'       => __( 'Parent Work Category' ),
        'parent_item_colon' => __( 'Parent Work Category:' ),
        'edit_item'         => __( 'Edit Work Category' ), 
        'update_item'       => __( 'Update Work Category' ),
        'add_new_item'      => __( 'Add New Work Category' ),
        'new_item_name'     => __( 'New Work Category' ),
        'menu_name'         => __( 'Work Categories' ),
    );
    $args = array(
        'labels' => $labels,
        'hierarchical' => true,
        'has_archive'   => true,
    );
    register_taxonomy( 'work_category', 'work', $args );
}
add_action( 'init', 'mav_taxonomies_work', 0 );
add_filter('post_type_link', 'filter_post_type_link', 10, 2);    
function filter_post_type_link( $post_link, $id = 0, $leavename = FALSE ) {
    if ( strpos('%work_category%', $post_link) === 'FALSE' ) {
      return $post_link;
    }
    $post = get_post($id);
    if ( !is_object($post) || $post->post_type != 'work' ) {
      return $post_link;
    }
    $terms = wp_get_object_terms($post->ID, 'work_category');
    if ( !$terms ) {
      return str_replace('our-work/%work_category%/', '', $post_link);
    }
    return str_replace('%work_category%', $terms[0]->slug, $post_link);
}

Also, you will have to write rewrite rules for your custom post type for your proposed URI structure to work.

Add the below code to your theme’s functions.php file:

add_filter( 'rewrite_rules_array','my_insert_rewrite_rules' );
add_action( 'wp_loaded','my_flush_rules' );    
function my_flush_rules(){
    $rules = get_option( 'rewrite_rules' );
            global $wp_rewrite;
    $wp_rewrite->flush_rules();
} 

// Adding a new rule    
function my_insert_rewrite_rules( $rules )    
{
    $newrules = array();
    $newrules['our-work/?$'] = 'index.php?post_type=work';
    $newrules['our-work/page/?([0-9]{1,})/?$'] = 'index.php?post_type=work&paged=$matches[1]';
    $newrules['our-work/(.+?)/page/?([0-9]{1,})/?$'] = 'index.php?post_type=work&work_category=$matches[1]&paged=$matches[2]';
    //print_r($rules);
    return $newrules + $rules;
}