WordPress theme - pagination issue

WordPress theme - pagination issue

I've installed a WordPress theme and pages 2,3,4,etc aren't working. They
come up with a 404 error that the pages cannot be found.
The url for page 2 is http://mysite.com/?paged=2.
After some messing around I've figured out how to get my pages to appear
but I have to manually type in the url to see them. For example, the url
to get page 2 to appear is http://mysite.com/?page_id=2&paged=2
How can I get it to go to this url automatically? Is it a permalink
problem (in my WordPress settings) or do I need to edit the pagination
code?
Any help will be so appreciated!
Here is the pagination code:
<?php
global $wp_query;
$big = 999999999;
echo paginate_links( array(
'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link(
$big ) ) ),
'format' => '?paged=%#%',
'current' => max( 1, get_query_var('paged') ),
'total' => $wp_query->max_num_pages,
'type' => 'list',
'prev_text' => __(''),
'next_text' => __('»')
) );
?>
</div>