WordPress post pagination on custom template not working

next_post_link will use the current query (which is the global $wp_query in your case). If you want to use them with other queries, pass them the maximum page number as the second argument. There’s an example in the codex.

For previous_post_link it doesn’t matter, because it’ll only show a link if you’re on a page other than the first – and if you are, there has to be a previous page. The link will show up when the paged parameter is > 1.