The place that was the first to celebrate New Year's day on January 1, 2000, was situated along the International Date Line, which runs through the Pacific ocean a little to the west (left) of Hawaii. Hawaii was therefore one of the very last places to celebrate the new year. See How Time Works for information on time zones and the IDL.
The very first place was probably, technically, in Antartica. Antartica was experiencing nearly full daylight at that moment, and there is a location in Antartica that is exactly on the IDL. Besides Antartica, the next place was probably the eastern-most island of Kiribati, called Caroline Island. Kiribati is a nice Island country near French Polynesia.
If you want to learn more, here are several helpful links: