next_posts_link
and previous_posts_link
use the global $wp_query
.
function get_next_posts_link( $label = null, $max_page = 0 ) { global $paged, $wp_query;
http://core.trac.wordpress.org/browser/tags/3.5/wp-includes/link-template.php#L1523
That means you need to do something like this to get those to work correctly.
$orig_query = $wp_query;
$wp_query = new WP_Query($args);
// the rest of your code
$wp_query = $orig_query;
If you are done with $wp_query
for that page load there is no reason to preserve it. It should be pretty easy to copy those core functions, modify them to accept a query parameter and create your own paging functions.