I had the exact same problem a while ago on one of my themes. My problem was that the theme used query_post to filter out some posts. This caused the pagination to fail.
I think this was the code that solved it:
<?php
if ( is_home() ) {
$paged = (get_query_var('paged')) ? get_query_var('paged') : 1;
query_posts("cat=-19&paged=$paged");
}
?>
cat=-19 was the category I wanted to remove. Try to just include it without cat=-19 if you want to include all categories.
The point of this code was to save the variable paged and include it again after I had made a custom query_posts so that WordPress knows what page the reader is on.