I finally made it work. Leaving the answer here in case someone else have the same problem.
<div id="content">
<?php
global $paged;
global $new_query;
$paged = get_query_var('page');
query_posts( array( 'cat' => 251, 'paged' => $paged ) );
$new_query = new WP_Query();
$new_query->query('cat=251&posts_per_page=3&paged='.$paged);
?>
<?php while ($new_query->have_posts()) : $new_query->the_post(); ?>
<?php the_title(); ?>
<?php endwhile; ?>
<div id="pagination">
<?php next_posts_link('« Older Entries', $new_query->max_num_pages) ?>
<?php previous_posts_link('Newer Entries »') ?>
</div>
</div><!-- #content -->