The All-Important Name
The place I like to start when naming a new character is the naming conventions for the world I'll be playing in. I think it really helps the continuity and "world flavor" of a game if everybody names their character using the same rules. Unfortunately, too few settings (both published and home-brew) have anything close to a consistent system for names. Some have no rules at all, and others have adopted the maddening practice of listing a handful of names from a given culture, as if that was all anybody would need. It sets up the absurd scenario where all characters from that culture have the same five names, or it forces players to try to cobble together original names by randomly combining syllables. This is ridiculously unrealistic. Given the list Ann, Jane, Katherine, Mary, and Susan, there's no way a person could possibly come up with "Elizabeth"--yet it is also a common English woman's name.
The travails of naming a character don't end with the naming conventions, though. The next thing to be considered, in my opinion, is your fellow gamers. Your characters will spend many hours together, sitting around the campfire talking of this or that. They will stand by one another through thick and thin. They will become Stalwart Companions, who--among other things--will be able to remember each other's names. Even if they're really, really complicated. You and your fellow players, however, will not be spending days at a time in each others' company (and if you do, you will probably use real names and not character names). Meanwhile, your fellow gamers have jobs and school and mortgages and kids and bills and other activities they're doing with their time. Their mind space is limited, so if you name your character Aelthlindigar son of Erdordigar son of Frokolditheld, you really shouldn't be too surprised when nobody can remember it (or pronounce it). And when gamers can't remember or pronounce your character's name, they will gladly substitute a word they do know (which is how I've come to call one of the other characters in one of my games "Helvetica").
When naming a fantasy character, I like to use "real" names. There are a couple of reasons for this. First is the thing about giving your fellow gamers a break; they're more likey to know and remember a "real" name than a made-up one. The second reason is that, in general, we aren't very good at making up names. Tolkein did it really, really well, but most of us aren't Tolkein and quite frankly suck at it. Real names have to be chosen with care, of course, so they aren't too modern-sounding and don't clash with the flavor of the setting. "No Bobs" is one of the rules in the Hero Builder's Guidebook, and I agree to a point. There's no reason, though, that a fantasy character can't be named Vladimir, or Sebastian, or Frieda.
One last trick I have is to use a nickname. This works well when the setting does have naming conventions, but those conventions lead you to made-up names that are going to be hard to remember. "I'm Kerindri Esveleen Evengold," one of my characters always says in introductions, "but you can call me Skeeter; everybody does." Her real name uses the naming conventions; her nickname ensures that the others at the table will remember what to call her. Rina, whom I've already talked about, is also using a nickname; her full name is Elanorina Pagomel. Another good use for a nickname is as a "placeholder" when you're not sure what your character's real name is. I played a character called "Swiftblade" for years; I had to name her in a hurry and I didn't know what kind of name she'd have. So I went with an "everybody calls me" nickname until I figured it out.
As a summary, here are the characters I'm currently playing (or have played recently), broken down by type of name.
Real Names: Euphemia, Grace, Poppy, Rhonwen, Sigrid, Talullah
Nicknames: Rina, Skeeter, Swiftblade
Made-up Names (yes, I do this occasionally): Tamarinth, Tulehara, Vorelle