The mines dept explanation seems feasible. I would be more inclined from the pic to think the gray stone is of the Basalt group and the stone formed on the perimeter of an ancient Lava flow, which were common in that region. Chip the exposed end off and you should be able to see if it's volcanic (Igneous) or sedimentary.
Cheers Wal.