Every now and then I run into the problem where pagination doesn’t work in a custom page template. The problem usually lies in my handling of query_posts.

The solution is to write the query as follows:

 4,
  'paged' => $paged
);

query_posts($args); 
?>

Enjoy!