Same problem for me on Centos 6.5
solved by
1, allowing .httaccess files to override stuff on your server
by editing thee file /etc/httpd/conf/httpd.conf
on server
in that file make sure this path is correct
# This should be changed to whatever you set DocumentRoot to.
#
<Directory "/var/www/html">
and set the AllowOverride below in that section to All
AllowOverride All
2,copy from the .httaccess.sample file from the magento download
<IfModule mod_rewrite.c>
############################################
## enable rewrites
Options +FollowSymLinks
RewriteEngine on
############################################
## you can put here your magento root folder
## path relative to web root
#RewriteBase /magento/
############################################
## workaround for HTTP authorization
## in CGI environment
RewriteRule .* - [E=HTTP_AUTHORIZATION:%{HTTP:Authorization}]
############################################
## always send 404 on missing files in these folders
RewriteCond %{REQUEST_URI} !^/(media|skin|js)/
############################################
## never rewrite for existing files, directories and links
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteCond %{REQUEST_FILENAME} !-l
############################################
## rewrite everything else to index.php
RewriteRule .* index.php [L]
</IfModule>
and add it to the .htaccess file in the top directory of your magento istallation (if it is not there then create one)
3, make sure rewrites are turned on in your admin->system->configuration->web->search engines optimization
done