I think they should start working on it now. Absolutley.
It will take a few years - hopefully (we don't want a rush job), so now is the time to start.
The sooner it's out, the sooner the modders are going to be able to play with it. The thing with the last two editions of civ is that it's the mods that really make the game, at least for me, and it takes another few years for the modding to really mature. So - if they start work on it now - I can look forward to full enjoyment in about 5 years or so. Civ 4 was released more than 4 years ago, and it was probably 6 years ago or so that development began, and it's only in the last year that the game has really reached its potential (for me at least).
I want them to take their time with the next release. I don't want a rush job, pushed out the door as fast as possible. I want them to experiment with different things so that when it's released, it isn't just a previous incarnation of civ with a new engine and graphics but has some new features to justify a new edition. Things that can't be done with mods in civ4 - like, say, a hex grid, or a throne room that has game functions, or other stuff.
So now is the time to start. They're looking at threads like this and deciding if they should start work on civ5 now or wait ... if you tell them to wait, we could be waiting a good long while before they even start (let alone release).