That is possible due to mod rewrite not working properly
To solve this check either mod_rewrite is enabled
if enabled then check your virtual host file and change it to following
Often virtualhost file contains AllowOverride none that actually restricts magento .htacess files to execute.
You need to put it to AllowOverride all.
Options Indexes FollowSymLinks MultiViews AllowOverride all Order allow,deny allow from all