Can posts_nav_link show post titles?

If I understood well to your question this should work.

<?php

global $paged;

if($paged > 1) {

$previous_post = get_adjacent_post(false, '', false) ;

$prev_post_title = get_the_title($previous_post->ID);

} else {

$prev_post_title = null;

}

$next_post = get_adjacent_post(true, '', true) ;

$next_post_title = get_the_title($next_post->ID);

posts_nav_link('&bull;', $prev_post_title, $next_post_title);

?>

Just copy and paste in someplace of your index.php.