Post page shows pagination but when clicked to next page - we get Page Not Found

I unlinked the link for a particular category of posts. The pagination used to work from one page to another. I have re-linked the category posts later in the day and now when clicking on the next or page 2, we get the error Page Not Found. I hadn't changed anything else except I was cleaning up some broken links on some of the posts.