I think that page has the pagination links wrong.
http://codex.wordpress.org/Function_Reference/previous_posts_link
previous_posts_link( $label , $max_pages );
Try just taking the $max_pages out, like:
<?php previous_posts_link('« Newer') ?>
<?php next_posts_link('Older »') ?>