According to the Codex:
taxonomy-{taxonomy}.php – If the taxonomy were sometax, WordPress would look for taxonomy-sometax.php
What I do when using custom taxonomy/custom post types is exactly what you mentioned in the second sentence. Make a page template and a page in the back end. Choose the template you built as the template to use when making your page.
EDIT
Just noticed that you’re getting a 404. In that case, check your permalink structure as well.
Again, from 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.