Cryptic does this in a very interesting manner. It has a character name, display name and then account. It's freaking awesome but a bit too complicated for this matter. Instead let us do something similar to what Steam does.
Create an account name, allow us to change a profile name and allow us an amount of name changes in any given time. So say we're allowed only three changes every year or better yet two. And this resets but does not accumulate. This is a better plan and if they enact a plan like this allow us to change our account name in case we want that to be our display name but only once may we change the account name, this offer will expire after a month when we accept the new EULA or whatnot.
I'll repeat in summary: Create an account, tie said account to a display name and let us change that display name twice every year.
I know this has been said, but I felt it needed to be said again.