Assuming you pick the absolute perfect combination, what is the lowest
possible number of humans it would take (in ideal environmental
conditions and without technology) to repopulate the species?  Could 12 do it?

Hmmm...you would need to have at least one female among the twelve ;)

Sure, 12 would do  - it worked in the past.  Question is:  how long it
would take to repopulate the species as it is today  - 6 billion, and
rising fast.

This answer to a similar question may be of interest:

http://www.answers.google.com/answers/threadview?id=378894

I'm thinking Jessica Alba, Jennifer Anniston, that secretary I had a
few years back who was just 19, Jennifer Connelly, Margaret Thatcher,
the Bush twins...

Oh, sorry, I thought you wanted a list.

yes 12 could but you could probaley 14
male female odds are 50 percent so if you have arond half and half
m=mom d=dad  number =kids
md      md       md     md        md  md          md md 
8        8        8       8       8       8        8  8 
then for every tow (md8,md8's)  there would be 64 childern 
making 512 then that times 8 and so on. i would take about 200 years or more

You could get a running start with 11 young women of childbearing age and 1 man...

Yeah, Cynthia, but after the first couple of months, he'll want to go
out for a drink with "the boys" and leave the girls to their knitting.
Max, did you consider that after 200 years, most of the first
generations would have passed away?
Myoarin