404 problem on archive pages

I have archive pages in my site, ( I have entered categories in menu) and all looks ok, except that when I go to page 4 or more in pagination I get the 404 page. The first pages are working fine.
Any suggestions? I have updated the permalinks also.

There is a problem in theme when used on last few versions of WP. Please follow these instructions:

1. open archive.php
2. find this line:

query_posts($query_string . '&posts_per_page=' . $postsPerPage . '&paged=' . $paged);

and change it to read:

query_posts($query_string . '&paged=' . $paged);

3. save