Pft, no. I mean, lots of evil queens seem to have black hair, but the originality within the character of your evil queen is way more important than her hair colour
I recommend you take a step back. If you're so worried about being cliché that you're concerned about whether to make someone black or blonde, you're probably thinking into this stuff waaay too much. Relax and have fun!
If half way through the novel you decide you get sick of her having black hair you can always have her bleach it.
Most evil queens possess black hair. But honestly, as long as your evil queen doesn't possess an overlarge nose, a cackling laugh, and an exotically exquisite name, you're good.
The color black symbolizes darkness. I think it all depends on how much emphasis you're exercising on her hair. As in, is its hue significant to the character's personality, that kind of thing. Of course, like Tenyo said, you can always dye it. I've never known a blonde villain besides Captain Queeg, although blonde's an innocent tone, but I think you could pull any hair color off.
I'm really creeped out. We keep running into each other.
“He leant tensely against the wall and frowned like a man trying to unbend a corkscrew by telekinesis.” – Douglas Adams
Cathy "Kate" Ames of Steinbeck's East of Eden is arguably one of the darkest, most twisted and fearsome characters in American literature to date. However, she is devastatingly beautiful, has pearly skin and heavy locks of blonde hair. Don't be afraid to break the mold!
I think there's a bit of a line you're confusing. Namely, when something is a trait and when something is a symbol.
Traits are, well, traits. Anybody can have them and they are simply there. It just so happens to exist that way. While it might be really common that way, it's nothing special.
A symbol, however, is special by its very definition. Take the fiery redhead. When you see a redhead in fiction, you figure she's going to have a temper. Her hair becomes a symbol for her personality. Black hair for a villain becomes a symbol when it reflects the evil within, or when you flip the protagonist to having their hair be blond. Then you're creating a light/dark parallel, and readers clue in.
The thing with a symbol is, the traits becomes representative of something more within the character. Check out the Hair Colours page on Tropes (warning: TV Tropes is a time sink) to see what some of the preexisting tropes are.
Let me just add that there's absolutely nothing wrong with using tropes. Tropes are tools. Knowing the tropes, however, can give you an idea for what readers expect whenever they see a certain trait. Usually cliche territory is when the trope is repeatedly pointed out, or when it's made the rounds so much people are tired of it.
A writer is a world trapped in a person— Victor Hugo
Ink is blood. Paper is bandages. The wounded press books to their heart to know they're not alone.
Honestly, I think it's difficult to come up with a completely 'original' villain.
But, the most common ones are usually the evil people who hate everything because their childhood was crap, people out for revenge, world dominators, mad scientists. Just off the top of my head.
