paginate_links() with Custom Taxonomy

Looks like I was missing 'paged' => get_query_var('paged') in the initial query.