We present ultraviolet (UV) color-magnitude relations (CMRs) of early-type dwarf galaxies in the Virgo cluster, based on Galaxy Evolution Explorer (GALEX) UV and Sloan Digital Sky Survey (SDSS) optical imaging data. We find that dwarf lenticular galaxies (dS0s), including peculiar dwarf elliptical galaxies (dEs) with disk substructures and blue centers, show a surprisingly distinct and tight locus separated from that of ordinary 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. We also find that the UV CMRs of dEs in the outer cluster region are slightly steeper than that of their counterparts in the inner region, due to the existence of faint, blue dEs in the outer region. We explore the observed CMRs with population models of a luminosity-dependent delayed exponential star formation history. We confirm that the feature of delayed star formation of early-type dwarf galaxies in the Virgo cluster is strongly correlated with their morphology and environment. The observed CMR of dS0s is well matched by 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.