I only know of two places to get a sandstone. And I mean only one spawns at the two areas. One is in the Savanah and one is in Stonetown.. Other than that I farm the bazaar to get more that way. They can be difficult to get in there also.
i know the best place. well you know haileys's observory in marleybone? the quest to azteca. well go in there and there will be one sandstone. go out, then back in and there will be another maybe in the same area or maybe a different one. but you don't have to switch realms when you go back in.
Try transmuting stone block into sandstone and sandstone into sunstone. Stone town has multiple stone block spawn points so you can just keep realm hopping. Savannah has two sandstone spawn points so those will take a little longer. Also, if you are level 60 and up, luska charmbeak in the waterworks drops both of them. If you have the right group and strategy, you can get to him in about 15/20 minutes.