Permalink works, then fails

Try flushing the permalinks. All you have to do is go to the Permalinks setting and save.

Thanks @andy!
It worked, but does this address the root problem?
I need to find a way to make sure this doesn’t happen again.

It’s really unclear when or why this happens. Fortunately recognizing it leads to an easy fix.