We have discovered nine ultra-compact dwarf galaxies (UCDs) in the Virgo Cluster, extending samples of these objects outside the Fornax Cluster. Using the 2dF multi-fiber spectrograph on the Anglo-Australian Telescope, the new Virgo members were found among 1500 color-selected, star-like targets with 16.0 < b_j < 20.2 in a two-degree diameter field centered on M87 (NGC4486). The newly-found UCDs are comparable to the UCDs in the Fornax Cluster, with sizes <~ 100 pc, -12.9 < M_B < -10.7, and exhibiting red, absorption-line spectra, indicative of an older stellar population. The properties of these objects remain consistent with the tidal threshing model for the origin of UCDs from the surviving nuclei of nucleated dwarf ellipticals disrupted in the cluster core, but can also be explained as objects that were formed by mergers of star clusters created in galaxy interactions. The discovery that UCDs exist in Virgo shows that this galaxy type is probably a ubiquitous phenomenon in clusters of galaxies; coupled with their possible origin by tidal threshing, the UCD population is a potential indicator and probe of the formation history of a given cluster. We also describe one additional bright UCD with M_B = -12.0 in the core of the Fornax Cluster. We find no further UCDs in our Fornax Cluster Spectroscopic Survey down to b_j = 19.5 in two additional 2dF fields extending as far as 3 degrees from the center of the cluster. All six Fornax bright UCDs identified with 2dF lie within 0.5 degree (projected distance of 170 kpc) of the central elliptical galaxy NGC1399.