What are the key qualities you look for in a candidate for startups?

I know that it is very difficult to gauge a candidate's attitude / work ethics from the start. What are the most important things you look for a candidate that will be fit for a startup software company?

• Willingness to do things they've never done (new technologies, random job responsibilities). Someone who regularly programs in their spare time with new technologies is good.
• Ability to pick up new skills quickly (similar to above)
• Gets things done ('big ideas' people are good, but you really need people who will execute at a startup). Look for someone who has a long list of projects at previous jobs.
• Prioritization - there's always too much work at a startup, knowing what's most important and gives the best bang for the buck is critical. Look for candidates that have done this in the past.
• Ability to tolerate uncertainty and vagueness. Many times you simply don't know what's best and you have to make a guess and go with it. You could give candidates coding/problem questions and see how they react. Do they ask more questions, freeze, start coding or give you a memorized answer? I'd go for someone who asks a few questions then makes a rough guess (and understands they are making a guess)
• Tolerates (even celebrates) failure. Everyone makes mistakes, the important thing is to recognize and act on them. Ask them about their biggest (or most memorable) mistake, see how they talk about it.
• Able to work with little management/direction. Someone who needs constant management and being told what to do will be dead weight at a startup. Look for someone who took the initiative for tasks and responsibilities at previous jobs.
• Able to take and give criticism well. Nothing kills small groups faster is someone who's a jerk or defensive. Try critiquing a candidate's answer and see how they respond.
• Excellent communication skills. Poor communication will kill a startup or project. Ask them to explain a very technical project they did. Read their blog and resume carefully. Take note of how they speak in the interview process.
• Some experience in the business field and customer understanding Since they will be building version 1.0, it's important they understand the problem and the customer. Having that insight will be super beneficial for them to help figure out solutions.
• Broad technical proficiency and experience I'm not too concerned about particular languages, just that they have a core understanding of basic CS topics and technologies. With only a few developers at a startup, they'll have to work on everything.

Hiring:

Phase 1: do they have integrity, intelligence, maturity (can they handle stress and setbacks)?

Phase 2: are they positive, energize others, courage to make tough decisions, and get things done?

Phase 3: why did they leave their last job? and the job before that? Make reference calls, and probe.

Jack Welch - CEO of GE - noted as manager of the century by Forbes (I believe, maybe Fortune)