Ill probably make a longer suggestion post once the dust settles, but this is a quick one after reading player comments on gamefaqs and other sites it seems that many people feel that "Campaign" signifies the meat of a game.  Sure you and I both know that sandbox mode is where its at in games like this.

Basically my suggestion is this, rename Campaign to something like "Tutorial Campaign" or just "Tutorial" but somehow many it more clear to the user that the Campaign will teach you the basics of the game, but letting them know where the true meat is as well.  Personally I might never touch the campaign, as I jumped straight into a sandbox and plan on some multiplayer with some friends in the coming weeks.   But for the average "doesn't follow this site daily and played every turn based strat since civ 1" player I think that "New Game" and "Campaign" seem somewhat ambiguous. 

Thats just my two cents.