By that logic 2000 is the last year of the second millennium, 2001 is the first year of the third millennium, 2002 the second, and 2003 the third.

The era started at year 1, and not year 0. So the new millenniums starts at years that ends with 1.