There was nothing wrong with my code above. I found the answer at the bottom of the Taxonomies page in the Codex:
If your site uses custom permalinks, you will need to flush your
permalink structure after making changes to your taxonomies, or else
you may see a “Page Not Found” error. Your permalink structure is
automatically flushed when you visit Settings > Permalinks in your
WordPress dashboard.
In my plugin I already had flush_rewrite_rules(); being called upon deactivation, and I had deactivated and reactivated it several times. The fact that this didn’t work really threw me for a loop.
But as soon as I visited Setting > Permalinks it all worked correctly!