Before you make that judgment call, make sure the problem doesn't have to do with the way you're communicating.
For execs who are coming from a technical background - especially first-time CTOs or those who have previously worked on teams where other execs were technical or at least savvy - it can be challenging to learn to communicate about technical topics in a way that non-technical people understand. I'm not saying that this necessarily is you, just that it's a common problem, and an important one to rule out.
Even if you're explaining the situation in a way that the CEO can understand the concepts, you may not be explaining the urgency or the repercussions in a way that makes sense to him, or in terms of stakes he cares about. Alternatively, he may be the sort of person who thinks everything other than negotiating with VCs is below his pay grade and it's really [the COO|the office manager|the CEO's personal assistant] who runs the company and get things done.
Tactic 1) try wrapping up your conversations with something like "in short, we need to do X within Y timeframe or risk losing $Z. What I need from you is to get the Acme contract signed by Friday. Can I count on that?" Then follow up about it Thursday, Friday, and Monday.
Tactic 2) talk to people who have been there a while and try to (not too overtly) work out who it is that really gets things done around here, and how they make that happen.
Tactic 3) find someone who's hungry and has lots of potential and initiative, plus involvement in a broad subset of departments (in a startup, the office manager or a senior person in operations is often a good candidate) and empower them to be the person who facilitates interactions between people and departments, makes sure people have what they need to succeed, and Gets Things Done. So that you don't have to be that person, and can concentrate on your own job. Only do this if you're willing to invest a lot of energy in what's still likely to be a crash-and-burn situation. If it succeeds, this is a huge win for your career, but the chances of success are low.
If that doesn't work and there just plain aren't good people in the company, or everyone at the top is clueless or doesn't care, there's no win to be had here. Get out. Go work with sane people.