Leche is right. Near Gran Via there are many record shops. At "Tres Cruces" street, there are 5 of them.

CD King is just opposite my hostel. I think they have a website but I can't find it.

Another one I've seen it's called "Killer's" and it's at Montera, 28.

Regards,

Antonio