Run through this guide to ensure you did every step:
https://drupal.org/getting-started/clean-urls
Make sure AllowOverride All is set in your vhost config. Double check that all of step 3 is set in your config file correctly. I had a similar issue on one of my servers and running through this guide fixed my problem.