Name rejected after deleting character

[Gorgowned]

I was trying to make a new character on the Red server using one of my old names, but it was rejected. I logged on to my old, unused account and found a bunch of old characters there, one of which had the name I wanted. I deleted him (and all the other characters) so that I could use the name on my current account, but when I did it was rejected again. The names of all the other deleted characters were rejected, too. Any help or explanation would be appreciated, thanks!