This discussion seems to be over, but for other frustrated folk:
<?php previous_post(); ?>
Didn’t work for me, even though I lifted it straight from the Codex. On the index.php page, I had to add an “s” to posts for it to work, as in:
<?php previous_posts(); ?>
This is on WP 2.2.
