WordPress sees underscore names as relating to post types and dashes as relating to taxonomies. Perhaps this has something to do with it? Also, have you flushed your permalinks recently (change the permalink structure to something else and then back)? It might be stuck in your database with the “sanitized” taxonomy name. This has happened to me numerous times with both taxonomies and post types.
