To add support for custom post types, open includes/tags.php and change line 70 from
$titles = $wpdb->get_results("SELECT post_title As name, ID as post_id, guid AS url, 1 cnt FROM ".$wpdb->prefix."posts t WHERE post_status='publish' and (post_type='post' OR post_type='page') and post_date < NOW() and post_title LIKE '%".mysql_real_escape_string($term)."%' ORDER BY post_title");
to
$titles = $wpdb->get_results("SELECT post_title As name, ID as post_id, guid AS url, 1 cnt FROM ".$wpdb->prefix."posts t WHERE post_status='publish' and post_date < NOW() and post_title LIKE '%".mysql_real_escape_string($term)."%' ORDER BY post_title");
In other words, just remove the check for post_type.