I don't think we need to make it only the central sea coast, just that that should be the "safe zone" If there are only 70 regions that means we can afford to have a few spaces inland free as well.
Attachment to specific lands is not as much of a problem as we might think. As it stands there's only one realm that never had lands bordering the central sea, Arnor. Even HD once held Caiylin.
I think anything over dramatic like whole realms teleporting will upset players more. Better to just establish "safe zones" and "wild zones" the latter being free of monsters and the former impossible to take over. For flavor just say a natural evolution has taken place, the more aggressive monsters that recklessly attack human settlements have died out leaving only more docile ones that stay put and attack only when threatened.
