I can kind of relate to what you're talking about. I haven't worked under someone with the CIO title. I've worked under people with titles like VP of Engineering and Chief of Operations (maybe that's another way of saying COO?). The culture that the people at the top foster makes all the difference.
From your description, this guy is incompetent. I don't mean from a technical standpoint (though that's possible, too), but in management. If he's insecure, he hates seeing people who appear to be more dilligent and competent than him. He may deliberately sabotage other people's efforts as a way of assuaging his insecurity. If other people are flustered or off balance, he doesn't feel like he's the only one who's in over his head.
I've experienced something similar to what you describe about him being forgetful and not communicating well. I was in a different position. I wasn't managing people. Rather, the incompetent manager I had dealt with things in a chaotic manner. I swear, sometimes he'd invite me into a meeting *with a customer* without giving me a heads up in advance about who the customer was and what we were going to be talking about. He had a habit of not properly prepping people for meetings. It was very disorienting. It drove me nuts. In fact, I'd say he didn't communicate well, period. He always had a cold, calm demeanor. So to those who weren't the wiser he appeared to be the one who "had it together", and I ended up looking flustered and frustrated. I could never tell if he was setting me up on purpose, or if things just turned out that way. His "cool, calm" personality may have been an attempt to smooth over the rough edges (he caused) with people he dealt with. In any case, he put on a good front.
I've read about this management type, and aside from notifying his superiors to the problem, you've got two options. You can either deal with it, or transfer out/resign. This may sound awful but the way I've read to deal with it (stay on the job) is to go along with his insecurity: don't try as hard, and don't highlight your accomplishments. Diminish your own importance, and praise him (lie). It's playing politics, going along to get along. It sucks, doesn't it? It sounds like you're an engineer, and you're seeing the dark side of the difference between engineering and management. To managers, playing politics goes along with the territory. You may have not realized it before, but it was always there.
If you don't play along and just keep going the way you're going, the problem is just going to get worse. Rest assured there will be people on your team who won't go along with it. You could start seeing defections/resignations from your subordinates unless something is done.
I was inexperienced with dealing with this situation, so the way I dealt with it was to get so fed up I resigned. Your work-style characteristics sound like mine, for the most part. Like I said, I was basically an underling with no management responsibilities, beyond technology. I only read about dealing with this situation later. Even then I don't know if I could've stomached it.
I submitted my resignation to the president of the company (it was a small company), and one of the things he told me was "I wish you had told me about the problems earlier." I was on good terms with him, but I didn't know him too well. He may have been excusing his role in the situation. After all, he hired him.
If you are on good terms with the CIO's superior, you may have a way out, if you approach him diplomatically. I would be professional about it. Don't just talk about your own frustrations. That makes it sound like you might be the problem. These are just suggestions. I haven't tried them, so I don't have experience with this. I'd say talk about the effect that this new CIO is having on the team. Talk about your attempts to work with him in a constructive manner and what the result was. The reason I say this is competent management will want people who are doing their due dilligence to help the company. You need to be taking actions that show you are trying to move the ball forward, strictly within your jurisdiction, and not acting as an obstruction to the company's goals. When you do that, and if the CIO is acting as the obstruction, it should be obvious to them. Maybe then, if his superior is truly concerned with the health of the company, your concerns will get heard.
What happened in my situation is I was one of the first people to leave. My leaving caused a "chain reaction" of sorts, because shortly thereafter other people were talking about doing the same thing. Within months, some others left. If you care that this does not happen, you should consider this possibility when considering what your next move is.
I kept in touch with a former coworker. A few years later he told me that this manager I had been complaining about before had almost destroyed the company. The manager finally got laid off 3 years after I left. They finally saw what I saw. I think there was some denial going on. It just couldn't be denied any longer when push came to shove. He was driving good people away, and he almost drove away customers, who had existing accounts with them. Believe me, if your CIO is treating you and fellow employees this way, he treats just about everybody that way. I imagine you're not alone in not liking this behavior, though his superiors may not see it. He may act differently around them.
Edit:
After reading some of the comments on here, I thought I should mention that after I left I pondered whether getting together with my manager, who I was having problems with, or the president, early on and having a one-on-one with him would've helped, and prevented what happened that led to my departure. Before I left I did have the opportunity to have a one-on-one with my manager. Apparently the president thought it would be a good idea if those working with him had a chance to talk to him about what had happened so far. For me it was too little, too late by then, but I went along with it. I conducted myself in a strictly business-like manner, and I diplomatically brought up some suggestions, particularly on his communication skills. He seemed receptive, and overall a nice guy. I was surprised. I found that he was someone I might be able to get along with personally. I just didn't like working with him. That can happen in life. I never knew if he took any of my suggestions to heart. I was out the door pretty soon after that, but as I said above, he was just bad news for the company.
Some post-ers said that "Tim" will need some "training from the shadows". I totally agree with this. What I've conveyed above were things I discovered over the course of a year. That was about the span of time between when he took over management duties and when I left. At first when things were going awry, I thought I was the one at fault, that maybe I should've known better. It wasn't until months later that I finally figured out that he was: fairly clueless, in over his head, and that *I* had to manage *him*, despite the difference in rank and title. I don't mean it like I had to give him tasks and direction, but rather I had to be careful what I did and did not tell him, because he would take what I said at face value. There was no filter whatsoever. It was impossible to have a discussion with him about project issues.
It was a difficult decision for me to leave. I'd say I was more than patient with the situation. There just came a point where "the straw broke the camels back". I had had enough. Having gone through that experience, there are probably things I could've done differently. In the future, should I run into this again, I figure I should at least give the possibility of positive change a chance. If it doesn't work out, at least I can go with the knowledge that I tried to deal with the situation. What I did in my first experience with this was just react. I didn't act proactively.