Helping out someone on WPSE.

wpse28770.php

<?php
/*
Plugin Name: wpse28770 Fixer
*/

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' );
}

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="%s">%s</a>', 
                esc_url( get_permalink( $v ) ),
                esc_html( $v->post_title )
            );
            $out .= '<li>' . $link . '</li>';
        }
        $out .= '</ul>';
    }
    return $out;
}