You can take blah as all hell name and stick on a character and, if they kick ass in game, the name will become something people respect. And you can take the most edgy, tough or powerful name and stick it on a character that never does anything of note and the name will not gain them even a bit of bonus respect.
So what does this mean? Don't stress a name. Just pick a name that's half decent then have your character make it a name worth remembering. After all, "A rose by any other name would smell as sweet." Or for those more easternly inclined, "The Tao that can be spoken is not the eternal Tao, The name that can be named is not the eternal name." :-)
It always bothered me hugely, so I feel your pain! To me the name is the most important part of the character. It has to be perfect. I usually pick an ethnicity and start google searching for baby names. And then pick an ethnicity or country and google for surnames until I find one that feels right.
Then otherwise I use Twilight Mirage naming conventions. My favorite good name for a character is Nightlee Haunting for a Star Wars RPG. My current Sindome name is the name of a Masks Character I made. :p
Parli Ment (Pack of parliment lights)
Seven Ecks (Sever vs Ecks dvd)
Ruby (Ruby Red Grapefruit juice)
Sliver (typo of Silver, for Bicardi Silver bottle, later became Slither when someone renamed me as a joke because my character created the Snakes)
Fengshui (Fengshui Rice Crackers)
Qosmio (brand of my laptop)
I always view the character name as more or less being your brand. If you PC name doesn't have a certain ring to it - it can be hard to be remembered. Name's like Null Void and Killian Rez were particularly effective examples where the cart was in front of the horse. Other times, I have found adopting the names other people provided to be just as effective.
Leverage your name to your character's manifest destiny. Building a decker or media personality with a strong person? Make sure it reflects that. Going to be an anonymous killer? Make your name as forgettable as anything else.