I think that completely depends on the startup. There are broad classes of startups in which UI design is not relevant, or at best a secondary concern that can be handled by a single member of the team.
Off the top of my head, I'd think that the UI would be of secondary importance in any startup that is writing systems software: if you can solve an important business problem, a fancy demo is impressive (and important!), but the basic problem you're solving often doesn't require a UI. For example, enterprise data integration (conversion between data stored in heterogeneous formats and systems), or natural language translation/processing. Many startups in information management / data warehousing: if you build a Teradata killer, the UI is certainly a component of your product, but it is pretty secondary. A startup building hardware (say, networking stuff) might not need to pay much attention to the UI, depending on the target market. etc.
If by "startup" you just mean "implementing the Web 2.0 idea-of-the-week", then yeah, I agree UI is usually pretty important.
Why "other than search"? Seems to me that at least half of the reason Google won was because every other search engined was tarted up with "portal" BS. That's UI.
So, since it's clear to me that search isn't one of those classes, and the examples given ("systems" stuff) is the area my startup is working in and I'm absolutely certain that UI is going to be 50% of the success or failure of our company, I'm not seeing any area where UI isn't vitally important.
One of the WFP2007 groups is working on a new language for mobile app development...and they're spending plenty of time on the "UI" even in that case. UI, of course, being anything that involves a user interacting with your system.
I guess someone somewhere in this thread is treating UI as "pretty things on a web page"...but UI hacking is important no matter what you're doing, if you want to sell it.
