Category URL issue

Hi there,
Lets try with steps below for M2 regenerates URLs rewrite for categories and associated products:
1 -- In categories management, create a new root category named ‘Temp Root Category’
2 -- Open Stores management, edit the default Store of the default Website and set the ‘Root Category’ form field to the newly added root category ‘Temp Root Category’ and click Save button.
3 -- Once done, open Stores management once again, edit the default Store of the default Website and set the Root Category form field to the main root category which you want to publish in the storefront again and click Save button.
Magento will regenerates categories and associate products URLs rewrite in this step. It might take sometime to complete this task (It depends on the volume of categories and associated products)
And then, re-index the data and clean the Magento cache.
And tell me know how it goes.
Regards,
Mall.

Hi Nick, 
Glad that it helps. 
In case you have any additional question, please do let us know here. 
Regards,
Ubertheme team