We propose the use of closely packed deep-subwavelength plasmonic coaxial waveguides that support backward propagating modes at visible frequencies, analogous to those in planar metal-insulator-metal geometries, as negative-index metamaterials. We show through simulation that the propagation properties of the metamaterial are determined by the dispersion relation of the constitutive waveguides. The metamaterial is polarization independent, is uniform in the propagation direction, and has a subwavelength character in the transversal directions. The transmission loss through the structure is also analyzed.