Two cents here. Similar situation happened to myself, except I wasn't the CTO but the de-facto "lead architect" of a major project/death march that had all of the stereotypical problems you read about again and again: product mismanagement, feature creep, overzealous salesforce, and heightened expectations reaching the impossible.

Much like yourself, I had been put in charge of an incredibly difficult project and somehow managed to grow a solid engineering team and build the system with them and get something out the door. 500k lines of C#, unit tests integration tests, the whole 9 yards over two years. We had finally launched (late and with much more baked in than accounted for) and started to tighten up iterations and bring in customer feedback. (Yes! We really had no customers using our system for two years during development!) I of course was under a lot of stress as feature backlogs grew and defects lists exploded because the software wasn't rolled out slowly and incrementally to clients but instead sold from day zero as if it was 100% rock solid.

So, as you probably had, I had my lunch with the CEO where I was being asked (ie told) that a new VP of Engineering position was going to be pursued to fix all the horrible problems plaguing the software development team. The problems which, at least from our perspective, had little to do with us since we pulled off not one but a series of those small miracles that only happen at 4AM by yourself in the tech room. However, taxed was I and naive, so I figured hey, what the heck, maybe I'll be able to write code some more if this magical hypothetical person can swoop in and take care of all that other nasty business like "talking to the sales guys and telling them not to sell features that don't exist."

So, we interviewed for this position fully unaware of what it was, exactly, we were looking for. Being young engineers if a candidate came in and had managed teams before and knew what unit tests were we were thrilled. We had no idea though what to look for, what red flags there were in hiring this person, so the third person or so who came in to talk to us ultimately was hired since it's hard to say no to someone who you don't even know how to judge. (And you can't, of course, just hire the first or second candidate that walks in the door because then you just look like you don't know what you're doing!)

So soon after this new hire we began interviewing for additional developer positions, but all folks that came in to meet us for interviews were developers this new VP of Engineering worked with in the past. As it turns out, the first candidate didn't know how regular expressions worked, so I said "no hire." The second, turned out, worked with a friend of mine some years back and spent days on end simply reorganizing the file structure of their svn repository, and so again, I said "no hire."

Well, they both still work there and I have long since left. Our system we worked on for years completely thrown out for yet another re-write from scratch, now to be done the "right way". The all stars on the team I helped build are all gone except one who has a family to support, all moved on to do startups or larger more innovative software companies.

A long story, yes, but I'd urge you if nothing else to consider the impact a hire like this can have on your entire team, since they will now be the ones making the hiring decisions. If you cannot trust them with that (and it's hard to trust anyone with that after just a few interviews), I'd say push back as hard as you can on this particular decision and try to, as PG says, "be resourceful" and bootstrap solutions from folks already in the organization you can trust.