Thought I'd try reviving this long-redundant thread.
When I've done "Edit King" and renamed all or most of the tribes, they seem to revert to their original names as soon as I change human players. Or sometimes, if I save the game and reload it later as the same human player, the original tribe names are again restored! In fact, the changes only seem to become permanent when you save the edited game in scenario format.
Is my computer the only one with this bug? If not, it's something for other scenario writers to watch out for.