Olá,

1 – No terminal do ubuntu digite:

php suapastamagento/html/shell/indexer.php -reindex catalog_product_attribute
php suapastamagento/html/shell/indexer.php -reindex catalogsearch_fulltext
php suapastamagento/html/shell/indexer.php -reindex catalog_category_flat
php suapastamagento/html/shell/indexer.php -reindex cataloginventory_stock
php suapastamagento/html/shell/indexer.php -reindex catalog_category_product
php suapastamagento/html/shell/indexer.php -reindex catalog_product_price
php suapastamagento/html/shell/indexer.php -reindex tag_summary
php suapastamagento/html/shell/indexer.php -reindex catalog_url

CUIDADO

Ao fazer isso todos os url_rewrite serão apagados e iniciados, qualquer um que tenha criado manualmente será apagado.