Al final parece ser que es un problema con los artículos y CMS que tienen acentos. En versiones anteriores estos acentos y/o carácteres extraños se trasladaban a las url amigables y es lo que da el error...
Se arregla con algo tan sencillo como ejecutándo a la base de datos la siguiente instrucción:
Para los artículos y CMS
UPDATE `ps_cms_lang` SET `link_rewrite` = REPLACE(REPLACE(`link_rewrite`, 'ñ','n'),'Ñ','N');
UPDATE `ps_product_lang` SET `link_rewrite` = REPLACE(REPLACE(`link_rewrite`, 'ñ','n'),'Ñ','N');
UPDATE `ps_cms_lang` SET `link_rewrite` = REPLACE(REPLACE(`link_rewrite`, 'é','e'),'É','E');
UPDATE `ps_product_lang` SET `link_rewrite` = REPLACE(REPLACE(`link_rewrite`, 'é','e'),'É','E');
UPDATE `ps_cms_lang` SET `link_rewrite` = REPLACE(REPLACE(`link_rewrite`, 'á','a'),'Á','A');
UPDATE `ps_product_lang` SET `link_rewrite` = REPLACE(REPLACE(`link_rewrite`, 'á','a'),'Á','A');
UPDATE `ps_cms_lang` SET `link_rewrite` = REPLACE(REPLACE(`link_rewrite`, 'í','i'),'Í','I');
UPDATE `ps_product_lang` SET `link_rewrite` = REPLACE(REPLACE(`link_rewrite`, 'í','i'),'Í','I');
UPDATE `ps_cms_lang` SET `link_rewrite` = REPLACE(REPLACE(`link_rewrite`, 'ó','o'),'Ó','O');
UPDATE `ps_product_lang` SET `link_rewrite` = REPLACE(REPLACE(`link_rewrite`, 'ó','o'),'Ó','O');
UPDATE `ps_cms_lang` SET `link_rewrite` = REPLACE(REPLACE(`link_rewrite`, 'ú','u'),'Ú','U');
UPDATE `ps_product_lang` SET `link_rewrite` = REPLACE(REPLACE(`link_rewrite`, 'ú','u'),'Ú','U');
Espero que le sea útil a alguien y no pierda tanto tiempo como yo...
P.S. - Con posterioridad he encontrado más tablas a las que les pasa eso... (que va a ser a todas). Voy a ir aquí pegando el código que lo soluciona... aunque se podría lanzar todo para curarnos en salud.
Para las categorías:
UPDATE `ps_category_lang` SET `link_rewrite` = REPLACE(REPLACE(`link_rewrite`, 'ñ','n'),'Ñ','N');
UPDATE `ps_category_lang` SET `link_rewrite` = REPLACE(REPLACE(`link_rewrite`, 'á','a'),'Á','A');
UPDATE `ps_category_lang` SET `link_rewrite` = REPLACE(REPLACE(`link_rewrite`, 'é','e'),'É','E');
UPDATE `ps_category_lang` SET `link_rewrite` = REPLACE(REPLACE(`link_rewrite`, 'í','i'),'Í','I');
UPDATE `ps_category_lang` SET `link_rewrite` = REPLACE(REPLACE(`link_rewrite`, 'ó','o'),'Ó','O');
UPDATE `ps_category_lang` SET `link_rewrite` = REPLACE(REPLACE(`link_rewrite`, 'ú','u'),'Ú','U');