404 Error for Custom post types Pagination

Hi,

Seems this error is pretty popular, i found some topics for it but nothing helped.

This is the story, i have a wp theme with 3 custom post types in it. When i use the default permalinks everything works just fine, but if i use any other permalinks structure, single pages for my custom post types or pagination don’t work (not both at the same time).

I printed out the wp_query var and i found that with %postname% permalinks structure, on pagination the query tries to get post_name=’page’

Here is the wp-query var on the first page:
WP_Query Object ( [query_vars] => Array ( [post_type] => testimoniale [post_status] => publish [paged] => 0 [error] => [m] => 0 [p] => 0 [post_parent] => [subpost] => [subpost_id] => [attachment] => [attachment_id] => 0 [name] => [static] => [pagename] => [page_id] => 0 [second] => [minute] => [hour] => [day] => 0 [monthnum] => 0 [year] => 0 [w] => 0 [category_name] => [tag] => [cat] => [tag_id] => 0 [author_name] => [feed] => [tb] => [comments_popup] => [meta_key] => [meta_value] => [preview] => [s] => [sentence] => [category__in] => Array ( ) [category__not_in] => Array ( ) [category__and] => Array ( ) [post__in] => Array ( ) [post__not_in] => Array ( ) [tag__in] => Array ( ) [tag__not_in] => Array ( ) [tag__and] => Array ( ) [tag_slug__in] => Array ( ) [tag_slug__and] => Array ( ) [caller_get_posts] => [suppress_filters] => [cache_results] => 1 [update_post_term_cache] => 1 [update_post_meta_cache] => 1 [posts_per_page] => 1 [nopaging] => [comments_per_page] => 50 [no_found_rows] => [order] => DESC [orderby] => wp_posts.post_date DESC ) [request] => SELECT SQL_CALC_FOUND_ROWS wp_posts.* FROM wp_posts WHERE 1=1 AND wp_posts.post_type = 'testimoniale' AND (wp_posts.post_status = 'publish') ORDER BY wp_posts.post_date DESC LIMIT 0, 1 [post_count] => 1 [current_post] => -1

and here is for page 2:

WP_Query Object ( [query_vars] => Array ( [page] => 2 [name] => page [post_type] => testimoniale [error] => [m] => 0 [p] => 0 [post_parent] => [subpost] => [subpost_id] => [attachment] => [attachment_id] => 0 [static] => [pagename] => [page_id] => 0 [second] => [minute] => [hour] => [day] => 0 [monthnum] => 0 [year] => 0 [w] => 0 [category_name] => [tag] => [cat] => [tag_id] => [author_name] => [feed] => [tb] => [paged] => 0 [comments_popup] => [meta_key] => [meta_value] => [preview] => [s] => [sentence] => [category__in] => Array ( ) [category__not_in] => Array ( ) [category__and] => Array ( ) [post__in] => Array ( ) [post__not_in] => Array ( ) [tag__in] => Array ( ) [tag__not_in] => Array ( ) [tag__and] => Array ( ) [tag_slug__in] => Array ( ) [tag_slug__and] => Array ( ) [caller_get_posts] => [suppress_filters] => [cache_results] => 1 [update_post_term_cache] => 1 [update_post_meta_cache] => 1 [posts_per_page] => 1 [nopaging] => [comments_per_page] => 50 [no_found_rows] => [order] => DESC [orderby] => wp_posts.post_date DESC ) [request] => SELECT wp_posts.* FROM wp_posts WHERE 1=1 AND wp_posts.post_name = 'page' AND wp_posts.post_type = 'testimoniale' ORDER BY wp_posts.post_date DESC [post_count] => 0 [current_post] => -1 [in_the_loop] => [post] => [comments] => [comment_count] => 0 [current_comment] => -1 [comment] => [found_posts] => 0 [max_num_pages] => 0 [max_num_comment_pages] => 0 [is_single] => [is_preview] => [is_page] => [is_archive] => [is_date] => [is_year] => [is_month] => [is_day] => [is_time] => [is_author] => [is_category] => [is_tag] => [is_tax] => [is_search] => [is_feed] => [is_comment_feed] => [is_trackback] => [is_home] => [is_404] => 1 [is_comments_popup] => [is_admin] => [is_attachment] => [is_singular] => [is_robots] => [is_posts_page] => [is_paged] => [query] => Array ( [page] => /2 [name] => page [post_type] => testimoniale ) [posts] => Array ( ) [queried_object] => [queried_object_id] => 0 )

Any idea what is the problem?