How do I display a list showing custom post types nested within a taxonomy?

Okay, so first off, I would rename your video category to something like video_category so it doens’t conflict with the built in category.

That said, the easiest way I could think to demonstrate this for you was with a shortcode.

Some initial prep, set up post types (for demonstration, delete the callas to register_post_type and register_taxonomy if you’re pasting this into your functions.php file) and add the shortcode.

<?php
add_action('init', 'wpse28770_add_types' );
function wpse28770_add_types()
{
    register_post_type( 'video', array( 'public' => true, 'label' => 'Videos' ) );
    register_taxonomy( 'video_category', 'video', array( 'label' => 'Video Category' ) );
    add_shortcode( 'wpse28770videos', 'wpse28770_shortcode_cb' );
}

And they we have the shortcode callback function which does all the work. First you need to get all the terms in your video_category taxonomy.

Next, loop through each term, fetching the posts in each one via a tax_query in get_posts. Then just loop through the posts and add them to a list.

<?php
function wpse28770_shortcode_cb()
{
    // get the terms
    $terms = get_terms( 'video_category' );

    // no terms?  bail.
    if( ! $terms ) return '';

    $out="";

    // loop through the terms
    foreach( $terms as $term )
    {
        // get videos in each term
        $videos = get_posts(array(
            'post_type' => 'video',
            'tax_query' => array(
                array(
                    'taxonomy'  => 'video_category',
                    'field'     => 'id',
                    'terms'     => $term->term_id,
                    'operator'  => 'IN'
                )
            )
        ));

        // no videos? continue!
        if( ! $videos ) continue;
        $out .= '<h2>' . esc_html( $term->name ) . '</h2>';
        $out .= '<ul>';
        // loop through the video posts
        foreach( $videos as $v )
        {
            $link = sprintf( 
                '<a href="https://wordpress.stackexchange.com/questions/38770/%s">%s</a>', 
                esc_url( get_permalink( $v ) ),
                esc_html( $v->post_title )
            );
            $out .= '<li>' . $link . '</li>';
        }
        $out .= '</ul>';
    }
    return $out;
}

You can just drop the above ‘wpse28770_shortcode_cb’ function in your functions.php file, and call it in whatever you template you like like this…

<?php echo wpse28770_shortcode_cb(); ?>

Here’s that whole mess as a plugin. Hopefully that at least gets you started!