pagination not working with permalinks

I’m using a custom post type and have a template with a query for the post type, it works fine when i use the default setting for permalinks but if i set them to anything else pagination breaks and the links go to a ‘page not found’ page.

Basically /?page_id=286&paged=2 works but photography/page/2 gets page not found.