The default tag cloud works with blog post tags only. You however are adding custom post type tags. Check wordpress.org for a plugin that will pull in tags from custom post types as well. There should be plenty available.

Thanks Mike, but I've been searching for a while and can't find any, can you suggest one please? What about "Popular posts" plugins?

Thanks,
Greg

This one should work:
http://wordpress.org/extend/plugins/ultimate-tag-cloud-widget/

The plugin says it should work fine. Here is a discussion about it if it doesn't work:
http://wordpress.org/support/topic/custom-taxonomies-with-custom-post-types

Hi Mike,

So I finally got this tag cloud working: http://indytube.net/

I found in your functions.php that you gave the taxonomy "type" to the custom tags and I used that in a custom post tag cloud. Now if you click on one of the tags, it goes to a page such as http://indytube.net/type/tagName, what is that page? How can I format it? e.g. choose a template with sidebar etc...?

Or even better, is there a way to automatically remove the "/type" part of the url?

I think I found the code in the tag cloud where the url is created, something like this:


$tag_link = '#' != $tag->link ? clean_url( $tag->link ) : '#';


Is there a function in PHP to remove a string from another string? Something like:


$tag_link = '#' != $tag->link ? clean_url( $tag->link ) : '#';
$tag_link = $tag_link.removeString("/type");


Thanks,
Greg

If you want a custom template for your tag pages, see here:
http://codex.wordpress.org/Post_Type_Templates

By default as you noticed, the tags are going to use the archives template. I don't have any code to customize permalinks via the functions.php file. You will need to check some wordpress hack sites as the permalinks are written via WordPress.