yeah it a bit hit and miss. I sometimes just can't get a texture looking right.I have yet to hand paint a decent rock texture.though it can be done.
I believe programs like bryce can create nice textures.
I sometimes render textures in 3dsmax also. you could create a realistic brick wall in max, setup the lighting nice and render to a 512x512 texture.
max has lots of procedureal textures like 'smoke' and 'stucco' for example . these can make good texture bases.

try and run an emboss filter in pshop on this texture. ie stylise\emboss.
try the angle 'up' and 'down' and you can get two different rock effects. this was doen with 'smoke' texture in 3ds max