There are thousands of hostales in Madrid, and it's hard to believe you'll have any problem in January. At that time you may even be able to book a more high end hotel at the same or lower price than a hostal. Hostales don't seem to have the resources to offer deep discounts and probably can fill up easier than a hotel with hundreds of rooms to fill, so sometimes you can live more luxuriously for the same price...especially in January.

Plug your dates into Venere.com or a similar site, and see what kind of prices you get. Venere has a separate section of Madrid hostales, so you can compare those prices against hotels and check availability.

The best book to go into detail about individual hostales was Sandra Gustafson's "Great Sleeps in Spain". Here you had dozens of these places in Madrid, Barcelona and Seville described by a woman with middle class (as opposed to budget) tastes, and I found that if she says a place is good it usually is.

Unfortunately the book has not been revised in some years, but I still find my copy useful. You may find a copy in the library that will give you some good suggestions.

Two years ago I stayed for 10 days at the Hostal Astoria on calle San Jeronimo. It was a great location, and my room was fine. I paid around 40 Euros a night. I found nothing at all to complain about in 10 days.