We show that waveguides with a dielectric core and a lossy metamaterial cladding (metamaterial-dielectric guides) can support hybrid ordinary-surface modes previously only known for metal-dielectric waveguides. These hybrid modes are potentially useful for frequency filtering applications as sharp changes in field attenuation occur at tailorable frequencies. Our results also show that the surface modes of a metamaterial-dielectric waveguide with comparable electric and magnetic losses can be less lossy than the surface modes of an analogous metal-dielectric waveguide with electric losses alone. Through a characterization of both slab and cylindrical metamaterial-dielectric guides, we find that the surface modes of the cylindrical guides show promise as candidates for all-optical control of low-intensity pulses.