It can be apache mod_rewrite that is not loaded.
Have you touched to apache (or any web server) configuration ?
Administration panel > Menu > Site -> Global Configuration -> Site: Search Engine Friendly URLs to No
If your website works, then the mod_rewrite module is your problem.