The only hostel (called "hostal" in Spanish) with a website anywhere near the Plaza de Colón in Madrid is Hostal Prim which is located just east of Colón in the Salamanca district. Their website still lists prices in pesetas and they only accept reservations by phone & fax.

Since Plaza de Colón is just on the edge of the "tourist district" you won't find too many hostels here. Plus, this area is somewhat "well to do $$$" so you'll mainly only find pricey hotels.

Good luck! And if you find someone in the area you're seeking please let us know here. Thanks!

Saludos, MadridMan