@Dead-i, according to oxwall, the problem is with mod_rewrite. They stated that: "...that means mod_rewrite is not properly configured. contact your hosting provider to do so." So, @Dead-i, can you check if mod_rewrite is properly configured?
I'm also having issues. Out of the blue, everything other than my home page returns a 404 error. Nothing changed at all, but it suddenly started doing that. I've only ever uploaded files to public_html. Where even is mod_rewrite?