New observations of 16 dwarf elliptical galaxies in the Virgo Cluster indicate that at least seven dEs have significant velocity gradients along their optical major axis, with typical rotation amplitudes of 20-30 km/s. Of the remaining nine galaxies in this sample, 6 have velocity gradients less than 20 km/s kpc^{-1} while the other 3 observations had too low of a signal--to--noise ratio to determine an accurate velocity gradient. Typical velocity dispersions for these galaxies are ~44 +/- 5 km/s, indicating that rotation can be a significant component of the stellar dynamics of Virgo dEs. When corrected for the limited spatial extent of the spectral data, the rotation amplitudes of the rotating dEs are comparable to those of similar brightness dIs. Evidence for a relationship between the rotation amplitude and galaxy luminosity is found, and, in fact, agrees well with the Tully-Fisher relation. The similarity in the scaling relations of dIs and dEs implies that it is unlikely that dEs evolve from significantly more luminous galaxies. These observations reaffirm the possibility that some cluster dwarf elliptical galaxies may be formed when the neutral gaseous medium is stripped from dwarf irregular galaxies in the cluster environment. We hypothesize that several different mechanisms are involved in the creation of the overall population of dE galaxies, and that stripping of infalling dIs may be the dominant process in the creation of dEs in clusters like Virgo.