Actually, both answers are correct, depending on your point of view. Something like this *shouldn't* be subjective, but it is and I'll tell you why.
Technically, going by our calendar, there was no year zero. The year immediately following 1BC was 1AD. So, by the calendar we use, the new millennium started in 2001, not 2000.
HOWEVER, here's the problem with that. The calendar we use is FLAWED and SHOULD have had a year zero! Yes, yes, I can just hear everyone yelling at their computer screens now, but calm down and use your fucking brains for a second.
First of all, whether Jesus was "the Son of God" or not, he was a living historical figure and the person whose life our calendar is based on. We don't start counting human age at "1 year" we start counting from ZERO! With a calendar based on a human life, when he turns ONE, the then year becomes ONE. We don't start counting at one when he's born. Were you "age 1" the day you were born? A good example of this contradiction is the fact that historical records show that Jesus died at age 33, in the year 33AD. Well, if you counted birth-to-age-one as year 1, then that's wrong: He died at age 33 in the year 34AD. Clearly, historians were counting the years along with his life (as we always have, up until about 1998 when people started to give a shit about this stupid debate).
Secondly, from a mathematical perspective, you hear idiots say "numbers don't start with ZERO, stupid!" Uh, were you asleep in the 8th Grade? YES, positive integers DO START AT ZERO, idiot! Ye Ole Number Line:
Now let's look at Ye Ole Calendar:
Uh-oh! Looks like somebody FUCKED UP!
Any mathematician should be able to tell you that everytime you count, the zero is "understood" to have come first, even though you don't say it. Sorta like how in English the "You" is "understood" to be at the beginning of a command. Y'know, like "Go fuck yourself" is understood to mean "You go fuck yourself." Well, "1, 2, 3..." is understood to mean "0, 1, 2, 3..."
Again, from the mathematical perspective, is the number "100" really "a hundred" or do the hundreds start with "101?" Take yourself back to the 3rd fucking grade when you learned place value, dork. The digit "1" is in the "hundred's place" therefore the number IS one-hundred!
The fact is, ladies and gentlemen, we DO always start counting from zero! The first positive integer is "0." The first integer in the tens is "10" (a 1 and a... ZERO!). The first integer in the hundreds is 100 (a 1 and... two ZEROS!). The first integer in the thousands is 1,000 and so on. If I said to you "count all the 30s right now" you'd go "30, 31, 32..." you wouldn't start at THRITY-ONE, you'd start with the ZERO!!!
So, the answer to your question is this. The calendar is flawed. It is the only place where we don't start counting at zero. That being what it is (a MAJOR flaw), then the millennium didn't start until 2001. However, if not for the calendar having royally screwed up a basic rule of math (that positive integers start at 0), then the millennium SHOULD HAVE started at 2000. Because of this, I consider either answer to be correct. In reality, there WAS a year zero, but in our calendar there was not. Take that for what it's worth. Hopefully I've left you more confused than ever!
P.S. - Before anyone even asks about the whole "Back To The Future" thing where Doc Brown entered "0000" as the year... The fact is, any time machine that worked by entering a date, would already have to be programmed with our calendar and any real time machine would work by taking you a set number of years into the past or future. So, the time machine would have to read "December 25, 0000" and calculate (based on the calendar it's programmed with) how many years, months, days, hours, and seconds, it has to travel back. If it's programmed with our modern calendar, it won't recognize "year zero." If it's programmed correctly, it will. Doc Brown obviously knew what the fuck he was doing since he programmed the damn thing. Heh, ok, but seriously, get a life. It's fiction.
Update: March 19, 2007
It's worth mentioning, as an addition to this letter that, as I mentioned, our calendar (the Gregarian calendar) doesn't have a year zero. Apparently I didn't make that clear enough. I keep getting e-mails with people all like "You're totally wrong, there was no year zero!!!" No shit asshole, and I fucking said that IN MY RESPONSE! In the calendar that we use, there was no year zero. Period.
However, our calendar is not scientifically based. Let's take a look at something that is scientifically based. How about ISO 8601 or astronomical year numbering? The math HAS to be correct for those, because they're used by computers to calculate time intervals. And guess what assholes.... THEY HAVE A YEAR ZERO!
So, in conclusion, calendars that aren't based on the science of mathematics (such as the calendar we use) don't have a year zero. Calendars that DO follow mathematics DO have a year zero. In other words, year zero is logical and therefore correct. So go fuck yourself.