Have no restrictions to naming the character. Make it so whatever is the first name that someone thinks of for their character is the one they'll get. For instance....

When I made my first character, I knew I wanted to name him something that had to do with fire. The first name that came to mind was Inferno, obviously. Tried it... taken. Then I thought, oh, maybe Scorch. Tried it... taken. Pyro. Tried it... taken. NSinR8. Tried it... taken. Sparx. Tried it... taken. After several other tries, I finally sided with the name NFerno. Obviously, an odd take on the first name I tried. Now, seven game days later. I finally think of a name that I think wouldn't be taken. Britefire Now, I never liked NFerno as a name, but I've had to deal. That brings me with a second point. Make name changes free.

Really don't think that's gonna happen.