A millennium is a thousand years. The 21st century and the 3rd millennium began on January 1st, 2001, not January 1st, 2000. A simple calculation can show this. The first century began on January 1, 1 A.D. (there was no year 0; the early medieval scholars who created the system of years didn't have an adequate concept of zero), and the 100 years comprising that century ended on December 31, 100 A.D. The second century began on January 1, 101 A.D. The 20th century began on January 1, 1901 and therefore ended on December 31st, 2000. Therefore, the new century and millennium began January 1st, 2001.
In the sixth century A.D., Dionysius Exiguus (which means "Dennis the Humble"), a Greek monk who lived in Constantinople, created a calendar that started with the birth of Christ. Unfortunately, he made a small miscalculation as to what year that was. Jesus was probably born around the year that Dionysius called 6 B.C., not 1 A.D. Since this error is perpetuated to this day, the new millennium should perhaps have been celebrated somewhere between 1995 and 1997.
If you're interested in this, you might also be interested in how to calculate the day of the week, or in noon and midnight.