As a starter, I recommend you review the discussion on a similar question regarding custom taxonomies and custom post types: Fixing Pagination with Custom Taxonomy Archive.
You'll probably need to work with the global rewrite/query variables and arguments to get things to work correctly.
