Pagination is not working with custom query inside a homepage template

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('&laquo; Older Entries', $new_query->max_num_pages) ?>
        <?php previous_posts_link('Newer Entries &raquo;') ?>
        </div>

    </div><!-- #content -->