Okay, I solved this problem, and am reporting back on the assumption that other people will have it, as well. It actually had nothing to do with the presence of multiple loops.
In the admin “Reading” settings, “Blog pages show at most” can not be set to a higher number than your query demands, or the subsequent archive pages disappear. So, some of my categories query 5 posts while others query 15. The admin setting must be set to 5 or lower for these all to work.
This wasn’t the case in previous versions, and I certainly can’t see any value in it, which leads me to believe it’s a bug.