There was that issue during the purge where accounts were purged off Neo, but unable to be created again because they were on Monkey Quest and Petpet Park... it might be somehow tied to that, though it seems to be the opposite issue of what you are having. They still haven't fixed any of those purged names since the last purge, everyone is still waiting to be able to create them.