Before you try any of this check the armory for the name of a character that is in use, but not over level 10.
If it is under 10 it is likely to be a banker OR a saved cahracter name.
EG: Some guy on my server saved the name Worganfreman . He made a level 1 human and just left it there for Cataclysm. Saving names is against ToS so this is what I done:
Step 1. I Checked the armory and sure enough there were no characters on my realm with the name.
Step 2. Open a ticket to a GM stating your cause including that you have searched the armory. Also state this is against ToS (Probably not needed but I done anyway)
Step 3. He (should) have just done a check for you which could have 2 possible outcomes.
(1) That name is in use by an active character/ over level 1
(2) Hey hey! He has renamed that character to something similar (In my case to Worganfrema)
Step 4. Make a character with your new name and level him to at least level 2!
Congrats, if you made it past step 3 you now have an awesome name!