Is this returning anything other than 1?
$paged = ( get_query_var( 'paged' ) ) ? get_query_var( 'paged' ) : 1;
I suspect that it’s not getting set at all because there is not a rewrite rule that covers a url like
/product/$PRODUCT_NAME/page/XX
To get the paged query var populated you will likely need to add a rewrite rule for it.
