In reply to Pylon King Against Capit@lism:
I wouldnt call myself an expert on the area, but from what I remember im pretty sure its to do with the various compounds in the rock and how they react with water/air. And also in the way they were originally deposited. More clay/silt gives a yellowy brown colour, but if lots of organic compounds are present its greener, or bluey. And red is to do with oxidation of iron compunds (predictably!) I think black limestone can also occur when it heats up significantly.
Of course this doesnt answer the question of why quarried limestone specifically is turning black!