How easy pieces can lock up would depend very much on the design. First off, check the material description pages here at Shapeways, they specify minimum thinkness, allowable gaps, and what tolerances they have. Also, similar subjects have been variously discussed in the forums,
Full color sandstone is plaster bound with superglue, so it is fairly sturdy, including the colours if you varnish it. It should survive normal gamies handling, though perhaps not dropping the item on a hard floor. Also, it is not flexible, so I don't know how well it will take to your purpose of locking pieces together.
Note that the colour of FCS is water-soluble, so don't use water-based varnish! Again, check the forums.
Greetings
Dragoman