Originally, the Romans numbered years ab urbe condita (a.u.c.), that is, "from the founding of the city" of Rome. Had this early Roman calendar remained in use, January 14, 2000 would have been New Year's Day in the year 2753 a.u.c.
Following his conquest of Egypt in 48 B.C., Julius Caesar consulted the Alexandrian astronomer Sosigenes about calendar reform since the a.u.c. calendar didn't meet the needs of the emerging empire. The calendar which Caesar adopted in the year 709 a.u.c.–now called 46 B.C.– was identical to the Alexandrian Aristarchus' calendar of 239 B.C., which consisted of a 12-month year of 365 days with an extra day every fourth year.
But Caesar wanted to start the year on the Spring Equinox or the Winter Solstice. However, the Roman Senate, which traditionally took office on January 1st, the start of the Roman civil calendar year, wanted to keep January 1st as the start of the year. So Caesar yielded.
The Roman date-keepers initially misunderstood Caesar's instructions and erroneously held every third year, rather than every fourth year, to be a leap year. After some dispute, Augustus Caesar (Julius Caesar's successor) suspended leap years, reinstating them with the leap year of 4 A.D.
Another source of uncertainty regarding exact dating of days at this time derives from changes made by Augustus to the lengths of the months. According to some accounts, originally the month of February had 29 days and in leap years 30 days. February lost a day because at some point the fifth and six months of the old Roman calendar were renamed as Julius and Augustus respectively, in honor of their eponyms, and the number of days in August, previously 30, now became 31–the same as July–so that Augustus Caesar wouldn't be regarded as inferior to Julius Caesar. The extra day needed for August was taken from the end of February.
However, there's still no certainty regarding this, so all dates prior to A.D. 4, when the Julian Calendar finally stabilized, are uncertain.
The Roman abbot Dionysius Exiguus instituted the system of numbering years A.D.–short for "Anni Domini Nostri Jesu Christi"–in 527 A.D. He figured that the Incarnation had occurred on March 25, 754 a.u.c., with the birth of Jesus occurring nine months later. Thus, he designated the year 754 a.u.c. as the year 1 A.D.
There's a question whether the first Christian millennium should be counted from 1 A.D. or from the year preceding it. According to Dionysius, the Incarnation occurred on March 25th of the year preceding 1 A.D., with the birth of Jesus occurring nine months later on December 25th. Therefore, it's reasonable to regard that year, rather than 1 A.D. as the first year of the Christian Era. In that case, 1 A.D. is the second year, 999 A.D. is the 1000th year, and 1999 A.D. is the final year of the second Christian millennium, making 2000 A.D. the first year of the third millenium. So, by this theory, all those who celebrated the new millennium on December 31, 1999, had the right year.