Speaking for the various Witches' Stones in Perthshire:

The Witches' Stone at Monzie is supposedly named after Kate McNieven, who was supposedly one of the last witches to be burned in Scotland. She was burned in front of the hill that you can see in the background of one of my photos (the one with Scotty and Martin looking at the stone). Both Scotty and myself have left a bit about her in the folklore section:
http://www.themodernantiquarian.com/browse.php?site_id=3267

The Witch's Stone at Meikle Obney is supposed to have been dropped in its place by a witch carrying it on her broomstick!
http://www.themodernantiquarian.com/browse.php?site_id=2294

The Witch's Stone in St Martins parish is the place where Macbeth met the witches, and so took it's name from that:
http://www.themodernantiquarian.com/browse.php?site_id=3190

And the Witch's Stone at Straloch appears to have been named in a similar context to the many Druid's Stones, because it was the site of some old ritual:
http://www.themodernantiquarian.com/browse.php?site_id=2054

Best wishes
Andy
http://www.andysweet.co.uk/stones/