Prepend Slug to Custom Taxonomy and Post Type

I’ve been banging my head against the wall on this one all day. I’ve added a custom post type called “gemstone” and a custom taxonomy for that post type called “gemstone-shape.” I want to have permalinks that look like this:

For a single gemstone page
example.com/shop/gemstones/%gemstone-slug%

For a taxonomy page
example.com/shop/gemstones/shapes/%shape-slug%

I’ve tried every idea I can think of for the rewrite slug for both the post type and the taxonomies. No matter what I do, the URLs that are generated 404. I’m very careful to flush my rewrite rules before each test. Let me know if more details or code samples would be helpful. Thank you very much for any ideas or suggestions.