I stayed at Hostal Arias last October. It's nice & clean, pretty inexpensive, and in the Barrio de Santa Cruz, just a 2 minute walk from the Alcazar and Catedral. They also have 24-hour access so late nights aren't a problem...

Check it out: http://www.arrakis.es/~reina/