Pagination breaks on child-categories, works fine on parent-category

I was finally able to get this working! Here’s how:

What I had misunderstood (being a WP noob and all…) is that get_query_var('page') is for pages, and get_query_var('paged') is for posts. http://codex.wordpress.org/Function_Reference/get_query_varfor

So I replaced these two lines

$paged = (get_query_var('page')) ? get_query_var('page') : 1; // FOR PAGINATION
'page' => $paged, // FOR PAGINATION

with these two lines

$paged = (get_query_var('paged')) ? get_query_var('paged') : 1; // FOR PAGINATION
'paged' => $paged, // FOR PAGINATION

and removed the 'posts_per_page' => 5, parameter from my templates, then set the post limit in the admin under Settings > Reading

This wasn’t the final solution, however. Pagination was still returning a 404 on custom_post_type categories. The final fix was adding this patch: http://wordpress.org/support/topic/custom-types-category-pagination-404#post-1913902 to my functions.php file.

Now pagination works perfectly on categories, and child-categories, on all post-types.