http://interhotel.com/spain/es/localidades/1390.html is a good site to find a hostal. When I arrived in Barcelona I stayed at the Hotel Balmes (
www.derbyhotels.es) but it was expensive.
There's a place called Hostal Neutral which I walk by to go to work which looks good.
Let me know if you need more help.
-L