Ask YC: How did you choose a name for your startup?

Oh, we spent much time trying different combinations of short english words having any relations to what we do, but all the domain names were taken. Then we tried a world play on english and latin words and came to "talk" + "naut" (lat. for sail) = talkonaut.com, which I believe precisely represents our mobile chat/voip software we develop: talk while you go. We also discovered that there's a chinese word "taikonaut" meaning astronaut (cosmonaut). So we used the idea of "talk while travel in space" in logo and promo. I think digging some rare languages (greek, latin, japanese, maybe scandinavian) can give you interesting names as well.

You are not trying to pick a name. You are trying to build a brand. The canonical text on the subject is The 22 Immutable Laws of Branding.

The name, logo type, mascot, tag line etc should all be coherent and consistent.

Here's Steve Yegge on branding: http://blip.tv/file/319044/

it is easy, you take a bunch of popular sites and combine into one mega name.

Myfacebookinrtube.com

Microsoft (dot) Alcatraz.

Great domain right there!

I think that it is important to have a story behind the name it doesn't have to be something complex, but a sense of authenticity does come through.

The easiest way to do this (and advice elsewhere here in the comments) is to switch up different descriptors of your idea, businees, etc into something where you can get a free domain.

I did this for my startup, Fabjectory, and it was even written up by The Name Inspector:

http://www.thenameinspector.com/fabjectory/

- Mike