The funny thing about sample sizes is that they don't scale with population size. [Edited the part where I said they don't scale "much"... they don't scale.]
If you're studying a phenomena with less than 5% impact, you need 1000+ data points to reach 95% significance.
Looks like we just replied to nostrademons at the same time, but we slightly disagree. You say that the dependence on population size is slow (sqrt) but I say there is no dependence for most cases. Are you sure you aren't confusing the dependence of confidence on sample size as opposed to population size? See, e.g.,
If you're studying a phenomena with less than 5% impact, you need 1000+ data points to reach 95% significance.
http://en.wikipedia.org/wiki/Statistical_hypothesis_testing [Fixed link, deleted my incorrect comment.]