I registered a custom taxonomy 'genre' and created a custom template taxonomy-genre.php
works perfectly but
gives me 404 error. I dump $wp_query and I get:
public 'query' =>
'paged' => string '2' (length=1)
'genre' => string 'comedy' (length=6)
As everything is working except for the pagination, it sounds like you don't have enough posts with that category to have a page 2.
With any pagination in Wordpress (not just for custom taxonomies), you will get a 404 error if you try to access a page number that doesn't exist - it's the same as accessing any page that doesn't exist.
Example: if you have 15 uncategorised posts and show 10 posts per page (i.e. enough for 2 pages of posts), you will get the following:
(Apologies for the simplistic example! I'm sure you understood, but I thought I'd include it for others with less experience who may have the same problem)