• We have updated our Community Code of Conduct. Please read through the new rules for the forum that are an integral part of Paradox Interactive’s User Agreement.
As far as I know, you can't edit all your kingdom(s)' province names, but only some of them (you must own the county or something similar).
 
Problem is that renaming provinces does not work if you're a count or a duke. Only if you're an independent ruler, which sort of limits the freedom of a player and totally contradicts what the hints say (anyone who is the owner a holding (and also their own liege and above) may rename settlements). If you're an independent ruler, you don't have any "liege or above".

I posted a picture here:
http://forum.paradoxplaza.com/forum/showthread.php?586630-Cannot-rename-settlements
 
In my game I could rename a province, which I did (Connacht became Mayo). Then, in a later game as von Habsburg, I was not able to rename anything anywhere, but County Mayo still existed.

So it appears to me that the game is taking a re-named item from one game into the next game, and in that next game you cannot access the renaming process.