This time they're made at 276x276, scaled down to 138x138, with the idea being that there's a 10px margin for irregularity.
I also tested a bit with little cracks on the tile(compare down-right to up-left), it doesn't work too well if you make them too dark. Also, there's the problem of the 'escher-effect'. this was initially solved with a black line that's rendered on top of the wall-tiles, but if we want iregular tiles, we'd need to think of how to deal with that.
An example of easy recolouring without boring colours.
I discovered this technique while pixelarting.
It's like this:
you have the sprite.
You have one version of the sprite that is the main colour. Then you have a version of the sprite that is only the shadows. This one is coloured in the shadow-colour. This one is layered above the main colour with the multiply blending mode. Then there's another version of the sprite that's only the highlights. This one is coloured in the highlights colour, and layered above all others with the 'screen' blending mode.
http://tnypic.net/55a05.png(middle row is what I'm talking about. The second image and the third are layered with blending modes above the first to make the green stones in the second screenshot)
I'd explain how to substract the 'highlights' layer and 'shadows'layer from a greyscale image, but it's rather hard to explain, because it deals with manipulating the alphachannel.