I figured this problem out literally seconds before I posted the question, so I thought I would go ahead and post the answer here. I’ve noticed there is not a lot of consolidated help for this problem out there.
This will help you if your “Older Posts” or “Newer Posts” links give you a 404 error when trying to display custom posts on a page-template.
Here are the steps to solve the 404 issue (in most cases) if you are having it. Check after each to see if the problem goes away.
Step 1: Flush your permalinks
Go to settings => permalinks. Select default. Save. Test. Select your preference. Save. Test again.
Step 2: Check your query.
If flushing the permalinks doesn’t fix the problem, double check your query. Use the Codex (see: Pages > page of posts). You need to define the $paged variable and use it in your query options.
Step 3: Make sure your posts_per_page does not conflict with the default.
There are some folks discussing this as a bug in the wordpress core. Whether or not that is the case, the posts_per_page => x option can cause issues with pagination if x is less than the default option.
A hack-ish solution to this issue is to set the default to 1 (settings > reading > “blogs show at most _ pages”).
NOTE: At this point, I was STILL having the problem.. it was step 4 that finally fixed it for me.
Step 4: Make sure your page slug != your post_type.
In my case, I had post_type => 'news'. And the page I was using was www.mysite.com/news. This caused the conflict that ultimately goofed the pagination up. To fix, I changed my post_type to ‘news-articles’ and re-flushed the permalinks. The problem went away.
Hopefully this helps you if you experience the same issue. I have a feeling a lot of people fall into this snare – it’s easy to do, and it’s not super intuitive to figure out. (at least it wasn’t for me).