My friend was having this issue when he signed up on MXO about a week ago. The trick is to leave the character name screen open for about 15 minutes or so, and then try going through...
It was the exact same problem, even gibberish like "adfue4t92" would be "taken". Apparently this issue hasn't been fully resolved yet...
