I think the problem is that the previous_posts_link() and next_posts_link() are using the global $wp_query object. Try changing your code to something like this:
// save the original $wp_query object
$temp = $wp_query;
// create a new $wp_query object
$wp_query = new WP_Query($args);
while($wp_query->have_posts()): $wp_query->the_post();
// output your data here
endwhile;
// display previous and next links
previous_posts_link('Newer');
next_posts_link('Older');
// restore the global $wp_query object
$wp_query = $temp;