I've noticed that Gallup polls very often survey 1001, instead of
1000, individuals.  I was wondering if anyone knew where the
preference for 1001 came from?

Statistically, the move from 1000 to 1001 doesn't substantively change
the 3.1 confidence interval in the result, so I'd like to know what
the back-story or reasoning is behind their decision to get that extra
one respondent in the mix.

It's interesting to note this address for the Gallup organization:

1001 Gallup Drive, Omaha, NE 65103 USA 

http://www.casro.org/member_details.cfm?id=1252

pinkfreud-ga,  I noticed and got a chuckle out of that too.  It's one
of the things that led me to wonder if there was possibly just some
quirky backstory that went into the frequent 1001 sample.

I, too, had hoped for a quirky backstory, but I couldn't locate one. I
suspect that this is just a gimmick, along the lines of the pamphlets
that promise "101 Ways to Quit Smoking" and such. Adding a '1' at the
end is an attention-getter, and it makes the number seem less generic
(except for the fact that the adding of the 1 has become a bit of a
cliché in its own right).

I asked the folks at Gallup (via their web page's feedback form) and
got an email back with the answer:

"We set out to conduct 1000 interviews in most of our polls but
sometimes two (or more) interviewers may be on the phone when we
complete our last interview.  Rather than terminate an interview
midway, we complete the interview and include it in our final data."
 
It's less interesting than the hoped for quirky backstory or poll
marketing ploy ideas, but it does make a lot of sense.  :-)