Whatever name you choose, be careful. Names stick. You need a way to refer to things, and whatever you call something rapidly becomes its name. So if you're not sure what to call a startup, either call it "our startup," or choose a name so terrible that you're not tempted to keep it.
The right type of name really depends on the type of business you're building, and who your clients are. Despite the conservative nature of the construction industry, "Woobius" has worked out very well, helping to differentiate us from the standard (and somewhat boring) construction IT providers. If you were starting an accountancy firm, on the other hand, something like "Brown & Martin" would probably work much better!
Names stick once you start using them in public. While the startup is unannounced, you can toy with pretty awful names. The "awful name" for Woobius was "Citeworks". I'm glad we moved away from it!
