Cannot name character after deleted character

Recently I found out my level 18 nelf druid 'Tiradari' was deleted and no longer exists. I was mildly upset but I wasnt that far into my character so it was okay with me. So I went to go create a human warlock under the same name (its a name I love) and it says character creation failed. So does this mean that my druid still exists or did someone steal my name? Thanks!