I see… because it’s theme related, since you tried Default and it worked fine, you could try to replace the call for the navigation, using the one from the Default theme.
Unless you really love the theme you are using, and can’t live without it, if I were you, I’d rather pick a theme that works fine from the start.
If you want to keep it, you can try to replace in index.php, page.php, single.php, etc. wherever you find
<?php posts_nav_link(' — ', __('« Previous Page'), __('Next Page »')); ?>
with
<div class="navigation">
<div class="alignleft"><?php next_posts_link('« Older Entries') ?></div>
<div class="alignright"><?php previous_posts_link('Newer Entries »') ?></div>
</div>
and then add to the style.css
.navigation {
display: block;
text-align: center;
margin-top: 10px;
margin-bottom: 60px;
}
as taken from the Default theme.