I worked on this a little bit more and if I delete all the traces of the custom taxonomies and then recreate them only one will work at a time. Seems like a problem with permalinks and multiple taxonomies working at the same time. Without the permalink structure changed both the first taxonomy and the second will work i.e.
One last little bit of info on this. It looks like the Permalinks aren’t saved properly. I’m entirely unsure if this is an issue with Simple Taxonomies or a WP problem. One thing I’ve done is if I save something in the Tag base field on the permalinks menu then delete it right after all the permalinks for the custom taxonomies will start working again.