I usually make them up on my own with a bit of creativity thrown in. Most have interesting first names and mundane last names.
Keldaren: half-elf ranger. Came up with that one when the original name the guy who rolled the character didn't work for me. Never got a last name so I decided he to be a bastard child.
Rozhena Ashford: female cleric. Took a long time to give her a last name so I decided that she didn't use it because of her troubled past and didn't want to remember it. Started using it again when her diety called her by her full name. She got nicknamed "Roze" by another player because the player couldn't pronounce her full name.
Sharlanna Melbourne: The first name *may* be a real name but swiped a city out of Australia that a guy lives who writes his campaign stories on the WOTC boards.
Which brings me to...
Kendrik Tallen'drel: male human ranger. I blatantly stole this name from the Aussie's character, "Kendrik Larsen" and somehow got the last name out of my head one day. A friend said it sounded like something from "Dragonlance".... Whatever....
Kelstra Firehammer: Don't know where I got the first name from. Gets mispronounced/mispelled by the DM as "Kelestra"....

Typical dwarven last name.
A friend of mine had problems coming up with names for his paladin/cleric, so I sent him a link to a website (don't know the link) that had Old English and other names and he roamed the Roman names section and came up with "Vallidius". DM couldn't pronounce it so he slightly modified it to "Vallidus". She finally could pronounce the original right when he had to drop out of the game.
He had another paladin that he called Valerian. Don't recall the last names for either character. But alot of times we shortened it to "Val". Nicknamed him "Val the Valley Boy Paladin".
Another guy when we first started 3ed named his monk, "Roscoe". He never heard the end of the "Rosco P. Coltrane" jokes while he played that character....