If your Pagination is not working only one category page, Or you have problem like Pagination is working fine on first page and not working on second or third page then you need add this code in you functions.php file.

add_action( 'pre_get_posts', 'wpse5477_pre_get_posts' );
function wpse5477_pre_get_posts( $query )
{
    if ( ! $query->is_main_query() || $query->is_admin() )
        return false; 

    if ( $query->is_category() ) {
        $query->set( 'post_type', 'video' );//Here Define your post type.
        $query->set( 'posts_per_page', 6 );//Here you need to put number of post per page.
    }
    return $query;
}