This is a very interesting problem, and I think, a very common one for those who try to write fantasy stories.
The best thing, I think not only when it comes to naming characters but also to make up the whole story is to have many sources. I.E you do'nt read "The Lord Of The Rings" and then sit down and think that you're going to create a whole new story of your own. Of course little bits of the LOTR-world will eventually find their way into your own mind, and you will use them.
I recomend to find names in odd places, take a map and look up some names of citites and such in very distant countries, names of persons in died-out-cultures and so on, then paly arround with them, take away and add letters, do whatever like with it.
You could do it the hard way and make up your own language, that's what I did about a year ago, then you take the strangest words you can come up with (such as "gvork" or "eee") and give them meaning, its kind of fun:D
You could take your own name and try to figure out what it means, there are websites for that in swedish we have
www.svenskanamn.se where you can look up the meaning of your own name and then translate it to your language. You could end up with the most amazing results.
It takes time but it's very funny.
-Joe Vaaodvatnodr