Coming back after 2 years. No character name I choose will work.

I just came back after 2 years and noticed all of my characters on Icecrown have been flagged for a name change. I was able to change one of them without a problem, but my lvl 80 DK will not take any name I give it. For most of the names I attempt, it doesn't even give an error message, but just refreshes the box. When I attempt a really common name, it then gives the error message that the name is unavailable, so it seems like I am getting two different reactions from the server when I try to change the name. How do I fix this?

check on armory if that name is available for your realm
Now armory shows even lvl 1 character: http://armory.warmane.com/

I just looked them up. Some of the names are taken but a few are not. I just tried 2 of the ones that are not taken on the armory and it still says That Name Is Unavailable.