The development of methods for estimating HIV incidence is critical for tracking the epidemic and for designing, targeting and evaluating HIV prevention efforts. One method for estimating incidence is based on changes in HIV prevalence. That method is attracting increased attention because national population-based HIV prevalence surveys, such as Demographic and Health Surveys, are being conducted throughout the world. Here, we consider some statistical issues associated with estimating HIV incidence from two population-based HIV prevalence surveys conducted at two different points in time. We show that the incidence estimator depends on the relative survival rate. We evaluate the sensitivity of estimates to incorrect assumptions about the relative survival rate, and show that small errors in the relative survival can, in some situations, create large biases in HIV incidence. We determine sample sizes of prevalence surveys to estimate incidence with precision and show how the sample sizes depend on baseline prevalence, the relative survival rate, and the population HIV incidence rate. We find that even if the relative survival rate were known exactly, there are situations where prohibitively large prevalence surveys would be required to produce reliable incidence estimates. These situations can occur either when the baseline prevalence is large, the relative survival rate is near 1, or the population incidence is small. Because information on the relative survival rate may be limited or not specific to the population under study, we suggest an approach to empirically estimate this critical parameter by augmenting population-based prevalence surveys with a mortality follow-up sub-study. We determine sample sizes of the prevalence surveys and mortality sub-studies for this augmented design and provide the necessary R code (version 2.13.0) for sample size determinations. We conclude that caution should be exercised when solely relying on changes in prevalence as the method for determining HIV incidence because of the method's sensitivity to mortality assumptions and the very large sample size requirements in some settings.