Issue: All links throws 404 not found error after install

Solution:

Make sure you have a working .htaccess file, optionally you can take it from a fresh Magento version download.
Also check if mod_rewrite is enabled on your server. That can be done by reading the phpinfo(); from a script on your server.
Also you need to be sure that System -> Configuration -> Web -> Search Engines Configuration -> Use Web

Wish you success.