Why is it making me change my name, when the name is apparently not in use?

[ZohnoReecho]

Maybe an old character that doesn't exist anymore. If that's the case the name is probably locked to avoid issues.

[Inquisitor]

From the EULA:

3.5 Naming Right. You may not use any name or other intellectual property belonging to Square Enix or any other third party in your use of the Game (for example, naming a character after a celebrity, company, product, or superhero).

So it's possible that someone had been using those names on Leviathan and was reported, making the names invalid for that server.

The game doesn't appear to have a particularly large database of names that are automatically prohibited (http://eu.finalfantasyxiv.com/lodest..._tribe=&order= as an example), but once a copyright violation has been reported they do have to take action in order to protect themselves from possible legal action by the copyright holder.