We want to change the order of categories so they are different in our stores but every time we change the order in say the FRENCH store, the UK store is also changed.
Looking at the database it seems there is one table which powers the sort order. catalog_category_entity
Can this not be done for stores sharing the one default category tree?
We have used the 3rd party software emagicone for doing mass updates in the past and there is a discussion about this being an issue here http://www.novusweb.com/1622/e-commerce-technology/fixing-magento-category-order-problems/ but we definitely have the 'position' set on each category with a number and the table catalog_category_entity confirms this.
Any need for reorganization of categories in different store scopes means that you have to duplicate your categories under distinct root categories. Sorry - it's a limitation to Magento's tree modeling of the categories which ultimately resolves (as you noticed) to the global-scope sorting attribute on the entity table.
You can do that using custom attribute. in Magento 2. I think same could be done in M1.
Add new product attribute with seting "Used for Sorting in Product Listing" to Yes. Add new attribute to your attribute set.
Assing numbers for products.
Catalog => Categories => choice Category => change store view, and change "Available Product Listing Sort By" and "Default Product Listing Sort By" to use your attribute.