I just returned from Spain yesterday, our last leg of the journey being Madrid. We stayed in Hostal Adriano (50 euro per double room) and it was great! The building is being renovated, so the entry way and stairwell are totally destroyed and there is no elevator yet, but believe me, when you make the climb what you will find is great friendly service & adorable rooms (especially for a hostal!!) Clean, functional showers & rooms, and comfortable beds with down comforters. Make sure you ask for a double bed, or you will probably have 2 singles. They make the beds and will carry your bags if you ring the bell when you get there. Also, they called us a shuttle service to get us to the airport. There is a post dedicated to Hostal Adriano on this site , so take a look at what others had to say, too.
Good luck, and please excuse my spelling, I'm still a bit jet lagged.