The ENCODE project has funded the generation of a diverse collection of methylation profiles using reduced representation bisulfite sequencing (RRBS) technology, enabling the analysis of epigenetic variation on a genomic scale at single-site resolution. A standard application of RRBS experiments is in the location of differentially methylated regions (DMRs) between two sets of samples. Despite numerous publications reporting DMRs identified from RRBS datasets, there have been no formal analyses of the effects of experimental and biological factors on the performance of existing or newly developed analytical methods. These factors include variable read coverage, differing group sample sizes across genomic regions, uneven spacing between CpG dinucleotide sites, and correlation in methylation levels among sites in close proximity. To better understand the interplay among technical and biological variables in the analysis of RRBS methylation profiles, we have developed an algorithm for the generation of experimentally realistic RRBS datasets. Applying insights derived from our simulation studies, we present a novel procedure that can identify DMRs spanning as few as three CpG sites with both high sensitivity and specificity. Using RRBS data from muscle vs. non-muscle cell cultures as an example, we demonstrate that our method reveals many more DMRs that are likely to be of biological significance than previous methods.