Breadcrumb for Custom Post Types

Hello again,

When breadcrumb option is turned on, it works great for pages. But when I have CPTs the following behaviour is observable:

When in base taxonomy: SiteName / "Archive"
When in custom taxonomy: SiteName / "Archive"
When in custom post type: SiteName / CPT post title

I need to be able to show breadcrumbs in the following order:
When on base taxonomy: SiteName / Base Taxonomy name
When in custom taxonomy: SiteName / Base Taxonomy name / Custom taxonomy name
When in custom post type: SiteName / Base Taxonomy name / Custom taxonomy name / CPT post title

I guess I need help with helpers.layout.php gk_breadcrumbs_output() function.

It is important to emphasize that a CPT is always connected to only one custom taxonomy.

One more thing that might be of significance, I am using WPML for multi language translation of the site.