Only list categories that contain posts of a specific custom post type

Put the following in your functions.php:

function wp_list_categories_for_post_type($post_type, $args="") {
    $exclude = array();

    // Check ALL categories for posts of given post type
    foreach (get_categories() as $category) {
        $posts = get_posts(array('post_type' => $post_type, 'category' => $category->cat_ID));

        // If no posts found, ...
        if (empty($posts))
            // ...add category to exclude list
            $exclude[] = $category->cat_ID;
    }

    // Set up args
    if (! empty($exclude)) {
        $args .= ('' === $args) ? '' : '&';
        $args .= 'exclude=".implode(",', $exclude);
    }

    // List categories
    wp_list_categories($args);
}

Now you can call wp_list_categories_for_post_type('photos'); or wp_list_categories_for_post_type('videos', 'order=DESC&title_li=Cats'); and the like.