The first question (how are the tables generated?) is easy to answer. The acknowledgement on the Astropixels page says:
It is based on procedures described in Astronomical Algorithms by Jean Meeus (Willmann-Bell, Inc., Richmond, 1998).
For the second question (how accurate are the calculations?), there are 3 sources of error that I can think of:
- The procedure may be for a limited time span. Meeus' book does not mention what time span the formulas are good for, but the source from which the procedure was based on (Chapront's ELP-2000/82) used the years 1900 to 2000 to determine the variables in the equations. (See NASA Astrophysics Data System - The lunar ephemeris ELP 2000.) It is hard to know what the accuracy is when going backward or forward several hundred years. Mathematically, extrapolating beyond the chosen time span could be reasonably accurate, or it could be "completely wrong". (I did not read all of the Astropixels' pages, but I know that a lot of historical research was done when calculating the solar eclipse tables. So I would anticipate some cross-referencing between the Moon phases and eclipses. After all, you cannot have a solar eclipse unless you have a New Moon!)
- Time is based on the rotation of the Earth, such as GMT (Greenwich Mean Time), UT (Universal Time), or the time in a local time zone. This type of time is not consistent over long time intervals. The Earth's rotation slows down and speeds up which requires adjustments to our clocks. The motion of the planets is (more) consistent and runs at a steady rate. Astronomers call this type of time Dynamical Time (formerly known as TDT Terrestrial Dynamic Time or ET Ephemeris Time). The difference between UT and Dynamical Time is explained in the Astropixels' page Uncertainty in Delta T. The uncertainty in Delta T is over an hour for the year 2000 BCE, so the time of the phase can be off by this amount just due to the uncertainty of clock time (the Earth's "clock") versus Dynamical Time (the solar system's "clock").
- Computer languages can introduce inaccuracies. For example, it may not be possible to store the number of days, hours, minutes between now and the year 2000 BCE to full precision due to the limited accuracy of storing really large number. There are approximately 1.05 billion (1.05E9) minutes in 2000 years. In order to calculate a result 2000 years ago to a precision of 1 minute requires the ability to store a number such as 1,050,000,001 and 1,050,000,002. (I am not a computer expert, but these numbers can probably be stored easily and to a higher accuracy. The potential problem is that the procedure uses values of time, time squared ($T^2$), time cubed ($T^3$), and time to the fourth power ($T^4$)! Thus, numbers can quickly become larger than what the computer can store to full precision.)
When put all together, I would expect that the times 2000 years ago (or 2000 years in the future) may only be accurate to a couple of hours.