For myself, it was caused by changing the permalink structure. This resulted in a modification of, or in my case, the generation of a .htaccess file including rules for mod_rewrite.
Make sure in your host configuration file that AllowOverride is set to All to allow mod_rewrite to work its magic. I’m not sure how I overlooked that for a half hour.
I was running it on a test server of mine, and it ended up being the specific vhost. So be sure to check outside of your global Apache configuration file if you’ve got virtual hosts set-up.
There are advanced ways of configuring the processing rules for mod_rewrite and configuring AllowOverride, so if you want to enable without AllowOverride All, just google and learn. If you don’t know what you’re doing though, I’d suggest reading about mod_rewrite and AllowOverride from the get-go for a better understanding of what’s going on with mod_rewrite and how it’s used / permalinks.
