Successful startups go through a couple of phases as they grow. At each phase the skills needed from the team will change because the challenges to get to the next level are different. And the team will often turn over along the way. Not everyone who was there in the beginning will be there at the end. And that's okay. Now maybe you have the skills and experience to grow with the organization along the way or maybe you don't. Lots of people maybe can and maybe can't. Sometimes it depends upon where you are in your career. Was this your first time managing? Then maybe you need more experience and growth to be the CTO of such a large org. It can often feel like a demotion when you are passed over and senior positions are filled from the outside. I understand where you are coming from. I've been in your position.

Whether the CEO lied to you or not really depends upon context. When did he tell you this? Obviously things have changed as the company has grown. Perhaps he didn't foresee the need for a CTO at the time but now he does. Things change and the needs of the company change with them. And remember he himself is growing and learning as a manager. If he was inexperienced he probably just couldn't foresee the need. Also how realistic is it that a growing/successful technology company won't have a CTO? I find it unusual that it took until ~450 people to get one.

Where do you go from here? If you'd like to be CTO (of your current company or another) the first step is an honest self assessment of the skills and experience you'll need to attain and perform in the position. Second you'll want to talk to the CEO about where you fit in to the company and your room for growth. You'll need to convey your understanding of the need to bring in senior management but also convey that you feel that you can grow along with the org to accept more responsibility. See if you can lay out a plan to do that. If you don't like what you hear coming out of that process then its time to start looking around.

Ben Horowitz has a really good blog post that touches on a lot of this stuff. http://www.bhorowitz.com/demoting_a_loyal_friend