Hi,
Your issue seemed to be coming from the canonical urls. And you could have checked your settings under Configuration > Features > SEF url options, then if the option for canonical urls was set on "Use canonical and generate it if not specified", when the menu alias was set on "shop-now", if you had traveled through the product pages, it would have generated a canonical url.
So two options, you change the canonical url setting to not use the canonical urls, or you change them in the product pages.
An easier solution could be to let the option to generate them if missing, and via our mass actions (System > Mass actions) create a product mass action to clear the value of the canonical url column. This way the canonical urls will be re-generated with the new alias.
But since it's fixed for you already, even better !