Guessing this is a custom post type with a custom taxonomy yes?
Had problems with this on another site, this is what I used if its any help:
<?php
global $wp_query;
$big = 999999999; // need an unlikely integer
echo paginate_links( array(
'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) ),
'format' => '?paged=%#%',
'current' => max( 1, get_query_var('paged') ),
'total' => $wp_query->max_num_pages
) );
?>
Need this it the loop query too:
'posts_per_page' => ($paged < 2) ? 11 : 12,
'paged' => $paged