Bush and Putin both came to power in 2000, a year when their countries were scrambling to regain international respect, Russia from the chaos of the Yeltsin years and the US from the failed impeachment of President Clinton.