One trick I do is to take a common name from now a days and play with the spelling
Example:
I took the name “Emily” for one of my characters
and did this
Em’alei
So many times you can generate “sci-fi/fantatsy” names from current names and just play with the spelling a tad to make it look “old fashioned”.
Baby name books and websites and a little “phonetic” spelling and you ca have traditional sci fi names that are easily read.
Or just call everyone Bob. 
My wife has a bunch of books by Elizabeth Haydon. The name of Haydon’s heroine is (and I am not joking) “Emily”. You don’t have to use terribly fancy names. Hell, one of the supporting characters in my project had the name “Eddie Van Helsing”, until my wife insisted that I change it.
I have a friend (I’m sure she won’t mind being mentioned) whose mother told the birth-certificate functionary that the baby’s name was “Dorothy.” Said worthy, incompetent, illiterate, or perhaps hung over, typed up the document “Doroyth,” a circumstance no one in the family noticed for some time. When later it was noted, they asked to have it changed, and were told they’d have to go to court and have a judge, etc. Already overburdened by the bureaucracy, the family said to hell with it. And Doroyth she remains to this day. (They pronounce it da-ROY-th.)
Phil
Interesting name story.
There was a professional Skater who’s name was
Natas Kaupus
Now many people began a hoopla years ago because
NATAS
spelled backward was SATAN which of course drove people to fear and gloom and doom.
Natas was intervied and the truth of his unique name came out.
When his parents were pregnant with him they thought they were having a girl. They thought on many names and it was a grueling process but they finally came to agree on the name
NATASHA
Now when he was born you could imagine the shock. Their poorr little Natasha was a boy!.
So because they spent so much time with the name and could not think of anything else to agree, knowing they could not have a boy named NATASHA they dropped the HA and named him NATAS never thinking of its spelling backward.
At least they did better than the parents one of our friends saw when she was a delivery-room nurse. Some of the names she saw on birth certificates included “Female” - and worse! And then, there were the infamous “Jell-o” twins: Lemongelo and Orangelo. I am not kidding!
My own not-unique-but-certainly-unusual spelling came about because my mother was a fan of Tony Curtis, and wanted me to be able to shorten my name appropriately. Apparently, no-one told her that “Anthony” gets shortened to “Tony” just fine… :\
(She even considered giving me “Curtis” as a middle name, but thankfully, clearer heads prevailed.)
I’m right there with you. My mother admired Jacqueline Kennedy, and wanted me to have the “Jackie” nickname. She didn’t like the sound of how Jacqueline is pronounced in French, and when she found Jacquenette in a footnote to Jacqueline in a book of baby names, that’s what I got. I figured my nickname was my own possession, and tinkered with the spelling accordingly.
sorry, read post below
well…you could just avoid the stereotypical fantasy names. take a historical approach.
if you know the setting of your story, even if it is totally original and not based on any geographic location in existence, think of a country that even mildly represents your fantasy world. than research names used in that country around the time your book will take place. even if you don’t use those exact names, you can get a feel for what your characters should be called.
i hated coma names! but an elf named Carl just wouldn’t fit…so i understand your struggle.
as for names in general. i usually name them after friends. the main female name i use is Elizabeth (my girlfriends middle name). so try that. and once people find out that their name is in your book, they will show their friends and make their friends read it. BAM, instant publicity.
Best of Luck!
The ‘fantasy naming game’ is driving me batty –
It’s becoming more frequent that whenever I come up with what I believe to be an uber-spiffy name – character, place, whatever – that there’s already a designer drug or a car bearing that name. It makes for a bit of craziness, it does.
And I have to agree with those who’ve voiced – here and elsewhere – discontent with the wildly impossible-to-speak-aloud names. I can’t say them without spraining my tongue, and I need to be able to pronounce those names so I can ‘hear’ the dialogue in my head. A sad little hang-up, I know.
But whenever such characters are mentioned between the quotation marks it throws me out of the story, every time without fail – that’s why I always try to spell names as fauxnetiklee as possible.
Start with
Tom
Dick
Harry
Bob
but not
Tom
Harry
Dick
Bob
This.
This is why we are reintroducing perigine falcons.
Speaking of falcons… falconcam-cmnh.org/news.php 
Here is the “local” breeding pair page. http://rfalconcam.com/rfc-main/mainView.php By local I do not mean around the corner from my house, but the city that I work in. I do not work for Kodak. Those birds sure do a good job. It is amazing to watch them actually snag a Wock on the wing. one minute a bunch of Wocks, next a puff of feathers and one less Wock.
As a surrogate (on behalf of my human,vic ), advocate of the general rehabilitation of Wocks, into the community as useful members of society, I feel the above is a little harsh. I doubt if the Wock in question sees the event, as of the genre: Amazing 
Wocks, so harassed, have been know to gather together, and then crap, en masse over the heads of falcons and senjays.
Fluff
Fluff,
As I am sure you are aware, the standard Wock is just a rat with wings. While we are “blessed” with an atypical Wock who has shown us that not all Wock’s are mere rodents, the Wock population is out of control in our area. One can not sit and eat a hot dog or hamburger in safety due to Wock attacks.
While I generally agree that rehabilitation is preferred to capitol punishment we are talking rodents. You know rats, mice, squirrels, and the like. Am am sure as a natural rodent hunter you would appreciate the falcons “Wock dispatch” capabilities. I dare say that if you were to witness them for yourself you might even venture to whisper “amazing” yourself.
…we av feelins too yno. 
rat
Most people have trouble coming up with good character names, But for fiction writers, it’s harder because you have to come up with a dozen or so character names for every single story. More: studymoose.com