About french names, there is also the "new" system: nouvelle orleans, nouveau mexique (nouvelle and nouveau are the equivalent of new. You have to use "nouvelle" if the next word is female gender, and "nouveau" if the word is male gender.
Depending on the french government, you can name systems with the ruling head of state. For example, louisiana was named for the current french king, louis XIV. If the french government is autocratic, it is a must have. If the french government is a democracy, you can also use old and famous president. For example you can use the name Gaule, which is an old world describing the french country in the roman empire, and is similar to De Gaulle (cf WWII). Or "nouvelle Gaule".
There is in france some cultural minority like corses (people who inhabit corsica), or "breton", in this case one can imagine a colony named corsica, or breizh, which is the name of the french region "bretagne" in the "breton" langage. You can use euskadi for the minority called "basque", there is also some old name from middle age, like navarre or labourd.
Hope it helps,
Hubert
Edit: some minor correction