I use the Everchanging Book of Names. It is random name generation software which uses a list of seed names and specific algorythms to come up with random names which have a similar cadence and feel. There are sets of seed names from dozens of real world and fictional cultures, so it is an excellent way of coming up with 'new' names which sound like they belong to a specific race or area. Because the names are created, I shouldn't think there would be any copyright or trademark problems (the software will occasionally build a name which duplicates one of the seeds, however). The larger the seed file, the better the created names feel like they belong to a given culture, and the more variety they will have. It is simple to create dozens of names and cherry pick your favorites. I have used the software for years (and even contributed a seed set or two). I collect and print out a hundred names for each culture in my campaign and keep them in my DM notebook, so I always have NPC names available on the fly for any nationality of NPC.
http://ebon.pyorre.net/