Since updating to 3.1 pagination of custom post type pages doesn't always work, it is actually really schizophrenic and randomly stops working, but will work on a page with a barely different title/url using the exact same page template file. Then the next day without making any changes the first one will paginate fine but the second one will not.
(By not working I mean mean it gives you a page not found when you click to view the second page)
I posted this same problem a few day ago in a different section on here but nobody had any ideas. http://wordpress.org/support/topic/31-breaks-custom-post-pagination?replies=1#post-2047198