Since the ultraviolet (UV) flux of an integrated population is a good tracer of recent star formation activities, UV observations provide an important constraint on star formation history (SFH) in galaxies. We present UV color-magnitude relations (CMRs) of early-type dwarf galaxies in the Virgo cluster, based on Galaxy Evolution Explorer (GALEX) UV data and the Extended Virgo Cluster Catalog (EVCC, Kim, S. in prep.). The EVCC covers an area 5.4 times larger (750 deg2) than the footprint of the classical Virgo cluster catalog by Binggeli and collaborators. We secure 1304 galaxies as members of the Virgo cluster and 526 galaxies of them are new objects not contained in the VCC. Morphological classification of galaxies in the EVCC is based on the optical image ("Primary Classification") and spectral feature ("Secondary Classification") of the SDSS data. We find that dwarf lenticular galaxies (dS0s) show a surprisingly distinct and tight locus separated from that of ordinary dwarf elliptical galaxies (dEs), which is not clearly seen in previous CMRs. The dS0s in UV CMRs follow a steeper sequence than dEs and show bluer UV-optical color at a given magnitude. Most early type dwarf galaxies with blue UV colors (FUV-r < 6 and NUV-r < 4) are identified as those showing spectroscopic hints of recent or ongoing star formation activities. We explore the observed CMRs with population models of a luminosity-dependent delayed exponential star formation history. The observed CMR of dS0s is well matched with models with relatively long delayed star formation. Our results suggest that dS0s are most likely transitional objects at the stage of subsequent transformation of late-type progenitors to ordinary red dEs in the cluster environment. In any case, UV photometry provides a powerful tool to disentangle the diverse subpopulations of early-type dwarf galaxies and uncover their evolutionary histories.