Problem Description:

This is a known problem with how WooCommerce generates the permalink for the shop, which is not actually a page but a dynamic archive. (your page is just a placeholder for the template assignment).

Answer:

Because your page can be called anything and have any ID, the link in the breadcrumbs depends on your shop page being linked correctly in WooCommerce Settings under the Product tab.

This should be working in all current versions of the above mentioned themes. Please ensure your theme is up to date!