High sales complexity isn't necessarily the kiss of death for a startup; it just means that you need strong sales talent early on (preferably in one or more of the founders). Sure, you do everything you can to shift your product as far toward self-service sales as possible, but at the end of the day, if you can't sell it without being out in the field, that means most other companies can't do it, either. Presto, barrier to entry.
My startup is definitely on the high complexity end of the spectrum; our sales cycle is anywhere from 3 months to 3 years. Right now, we have no direct competitors; this is probably at least partly due to the complexity of the sales process.