Ironically, the velodrome will take longer to build now that the London 2012 bid has been successful than it would have done if the games had gone to Paris. This is because much of the rest of the Olympic park will have to be built before the velodrome is constructed. If the bid had failed then none of this extra infrastructure would have been needed and work could have started much sooner.
A realistic start date is 2008-2009 as Gangmaker said.