I have successfully (though it took me hours to find a solution) got pagination for my custom post type, books. However, the pages linked, though the slugs are correct, give me 404 errors. I've tried everything, even changing the way pagination was achieved and flushing my rewrite rules several times.
Example:
http://www.thatrenee.com/books/ works fine, while
http://www.thatrenee.com/books/page/2/ gives a very not so welcome 404 error.
Is there anyone that has successfully implemented paging of custom post types so that the subsequent pages display the content correctly?