As someone who has worked on numerous projects from a wide variety of media (art, design, indie film, music, among others), I would like to suggest that you can never start a project too early. You can most definately finish it too late, however. If you're not working with a deadline, then it is entirely possible to underfinish a project and it will stink like a dead fish.
My advice to you, even if you're not going to do anything else on your game yet, is to write a one-page synopsis of the story, an additional page describing your main characters, and maybe a paragraph describing how you want your art direction to go. Even beyond that, there is a lot of work you can do without the CGE.
Apparently Coldstone has recently hit the alpha mark, and while I'm hoping to be on the beta team, I'm not going to count on it. But, I've already started my first game; I have the story fleshed out, I've started to model characters in a 3-D program, I'm drawing maps in a sketchbook while I ride the subway to work, and I recently started writing dialogue. I know that before I get my hands on the CGE application, I can still finish up dialoge, get all my art ready, have maps done in detail, and write music.
Of course, it would be nice to get a full feature set for Coldstone, too, because it would suck to have a cool idea that the engine couldn't implement.
------------------
--You notice that you have been turned into a pile of ashes.