I'm not sure, but I don't think you need to make a new character and log into a server with said new guy anymore. Doing so may be what is making it come up as unavailable, even. Try deleting those new characters on the website, then changing your name again, maybe? Also, name changing has become more strict recently, and is done by hand as far as I know. Only for fixing typos/removing tags. Hope one of these things is the source of your issue.
