Drupal doesn’t create clean links – checkbox doesn’t do anything
1)enable rewrite module on apache.

a2enmod rewrite

(to disable type a2dismod rewrite)

2)Set directory permission.
You must find the file that sets permission of each directory for apache. In my case it was /etc/apache2/sites-enabled/000-default
edit the page so that the directory that you will be using to serve webpages has "AllowOverride All". My file contains the following:

Options Indexes FollowSymLinks MultiViews

AllowOverride All

Order allow,deny

allow from all

3)Just restart apache and it should be working:
/etc/init.d/apache2 restart

There are several other checkpoints to fix this issue. All the points are discussed here