Quick fix for those having the same issue with WP permalink. You may have rebuild .htaccess, but this problem persists.

Try this, edit /etc/apache/apache2.conf

Under directory /var/www, make AllowOverride All instead of None.

Hope this will save time for some of us.