ToniG, they may not have been full for October. Some hostels won't take reservations so far in advance and instead will tell you just what Hostal La Macarena told you. I'm not saying they're NOT full but this is what owners do sometimes. Unless you make firm reservations with another, try them again 4-6 weeks before your departure.

OR, maybe you'll be in Madrid during the big Fería de Otoño bullfighting festival? Good luck!

Saludos, MadridMan