Previous posts link not working

I have a weirdness…

My post_nav_link tags are not working in my main index template. Here’s the code:

<div class="navigation">

<div class="alignleft"><?php posts_nav_link('','','&laquo; Previous Entries') ?></div>

<div class="alignright"><?php posts_nav_link('','Next Entries &raquo;','') ?></div>

</div>

I have done the usual troubleshooting. I deactivated any recent plugins, I repaired my DB tables, I checked and rechecked my template. The same link on ARCHIVE pages work fine. I also cannot enter manually any ?paged=X URLs, they just show the main page and the X posts I set on the front page in the site options.

Any advice?