tinako

I seem to have fixed my problem.

What didn’t work:
I renamed my theme and reinstalled it.
I removed all my plugins.

Then, figuring this theme must work for others, I checked out http://www.twostudsandahammer.com, who just posted a query, and saw that their URLs were different (and their category next page works).

I changed my Permalinks (Settings menu) from Default to Post Name and it now works.