After a looong day debugging thru wordpress core, I managed to solve this issue.

Basicly, you CANT have a PAGE and a CUSTOM POST TYPE with the same name. If you do, the permalink rewrite rules will get confused and trigger a 404.

A very simple solution I’m using is: The page that lists the custom post types is called in plural (eg. products) and the actual post type name is in singular (eg. product). So they dont conflict and it’s all fine.

Done Done!
Hope this will save people’s time.

See  WordPress support forums: http://wordpress.org/support/topic/pagination-with-custom-post-type-listing?replies=23#post-1637753

I did a function as well that you can use it instead of the wordpress query_posts(), this function does exactly the same but adding some more stuff that is need to pagination work correctly on custom post types pages:

http://rafaelxy.pastebin.com/VtHQEkH7