Magento 1.4 – Use Categories Path for Product URLs Not Working

Here's a number of options:

1. Update the URL keys the same way you updated the product titles.
2. Export, transform values, import.
3. Unset the URL keys programmatically and have them regenerated automatically.

While the former are rather self-explanatory, this is how the scripted approach looks like:

$collection = Mage::getModel('catalog/product')->getCollection();
$collection->setStoreId($newStoreId);
$collection->addStoreFilter($newStoreId);
$collection->addAttributeToSelect('*');

foreach ($collection as $product) {
    $product->setStoreId($newStoreId);

    // disable adding entries to url rewrite rules (optional):
    $product->setSaveRewritesHistory(false);

    // if there are already url keys on store scope:
    $product->unsUrlKey();

    // otherwise, if the new store uses default values from parent scope:
    $urlKey = $product->formatUrlKey($product->getName());
    $product->setUrlKey($urlKey);
}

$collection->save();

By default, URL rewrites are added to the system. You can optionally turn that behaviour off.

Unsetting the URL key will only have effect if the product already has a URL key in the new store scope. If the product pulls its URL key from a website or default scope, the new URL key must be set explicitly.

You must follow in your admin, Store -> Configuration -> Catalog -> Catalog -> Search Engine Optimization -> Use Categories Path for Product URLs, you must change to No, and you have to make sure that in the Website and Store View is No.

After that, you must reindex and refresh the cache.