Yo tenia todo correcto, con prestashop 1.6, apache bien configurado, hice todos los pasos, de borrar el htaccess, etc.
Lo ultimo que hice fue modificar el htaccess con url amigable activado
En el htaccess eliminé las lineas de <IfModule mod_rewrite.c> y </IfModule>