Analysis of the coalescent structure of a population may provide information useful in mapping disease loci. Current coalescent-based genealogy samplers require haplotyped data, but haplotypes are not always available, and it is not practical to sum over all haplotype assignments for large data sets. We describe a method of adding haplotype re-evaluation to the sampler, so that it samples not only among genealogies explaining a given haplotype configuration, but also among different haplotype configurations. Several different haplotype-rearrangement strategies are considered, but the simplest-inverting the phase of a single site in a single individual-appears to be the most successful. The straightforward haplotype sampler does not mix well; heating approaches can greatly improve its performance.