There have been many polls of who's in the lead in the presidential
race, but I was surprised that a national poll of less than 800 was
used to determine who's in the lead.  Can someone point me to
critiques or support of the accuracy of polling with such a small
sample?

Firstly the key point here is that the sample taken is
"representative".Just like a doctor who takes a sample of blood (
doesnt pump out the whole bloods out of you) for diagnosis.

The margin of error due to sampling decreases as sample size
increases, to a point. For most purposes, samples of between 1,000 and
2,000 respondents have a sufficiently small margin of error that
larger samples are not cost-effective.

If there was even a sub grouping required within these (say you wanted
to find out what percent of the people who say they vote for democrats
also are from a particular minority) then you would definitely need a
larger sample size.

In general, the margin of error in a poll is inversely proportional to
the square root of the sample size.  A poll of 10 people would have a
standard error of 1/sqrt(10) =~ 31.6%.  A poll of 100 people would
have an error of 1/sqrt(100) =~ 10%, a poll of 1000 people would have
an error of 1/sqrt(1000) =~ 3.16%, and a poll of 10,000 people would
have an error of 1/sqrt(10,000) =~ 1%.

As you can see, one quickly reaches a point of diminishing returns in
terms of reducing the standard error once the sample size reaches
several hundred people (assuming the people chosen are a truely random
sampling).

See http://www.publicagenda.org/polling/polling_error.cfm
http://www.studyworksonline.com/cda/content/article/0,,EXP545_NAV2-76_SAR542,00.shtml
http://whyfiles.org/009poll/math_primer.html